Minimize max frequency difference of 0 & 1 by dividing Binary String into K disjoint Subsequence
Given a binary string S of size N and an integer K, the task is to divide S into K disjoint subsequences(empty subsequences are also allowed) such that the maximum absolute difference between the number of 0s and 1s among these subsequences is minimized.
Example:
Input: N = 7, K = 5, S = “1010100”
Output: 1
Explanation: Suppose the partition is {“10”, “10”, “0”, “10”, ” “}.
The respective absolute difference between
number of ones and zeroes are {0, 0, 1, 0, 0}.
The maximum of which is 1.Input: N = 6, K = 2, S = “101111”
Output: 2
Approach: The problem can be solved using the below mathematical idea:
Find the absolute difference between number of zeroes and ones present in the binary string, divide it in K parts by taking value of ceil(difference/K)
Follow the steps to implement this idea:
- Initialize variables ones and zeros both to 0.
- Iterate over the string and increase the count of ones and zeros according to the characters of the string.
- Find the absolute difference between ones and zeros and store it in variable diff.
- Return ceil(diff/K).
Below is the implementation of this approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; int minAbsDiff(string S, int N, int K) { int zeros = 0, ones = 0; for ( int i = 0; i < N; ++i) { if (S[i] == '0' ) ++zeros; else ++ones; } int diff = abs (ones - zeros); int ans = (diff + K-1) / K; return ans; } int main() { int N = 7; int K = 5; string S = "1010100" ; // Function Call int ans = minAbsDiff(S, N, K); cout << ans << endl; } // This code is contributed by ishankhandelwals. |
Java
// Java code to implement the approach class GFG { // Function to find the minimum // absolute difference among subsequences public static int minAbsDiff(String S, int N, int K) { int zeros = 0 , ones = 0 ; for ( int i = 0 ; i < N; ++i) { if (S.charAt(i) == '0' ) ++zeros; else ++ones; } double diff = Math.abs(ones - zeros); int ans = ( int )Math.ceil(diff / K); return ans; } // Driver Code public static void main(String[] args) { int N = 7 ; int K = 5 ; String S = "1010100" ; // Function Call int ans = minAbsDiff(S, N, K); System.out.println(ans); } } |
Python3
# Python3 code to implement the approach def minAbsDiff(S, N, K) : zeros = 0 ; ones = 0 ; for i in range (N) : if (S[i] = = '0' ) : zeros + = 1 ; else : ones + = 1 ; diff = abs (ones - zeros); ans = (diff + K - 1 ) / / K; return ans; if __name__ = = "__main__" : N = 7 ; K = 5 ; S = "1010100" ; # Function Call ans = minAbsDiff(S, N, K); print (ans); # This code is contributed by AnkThon |
C#
// C# code to implement the approach using System; public class GFG { // Function to find the minimum // absolute difference among subsequences public static int minAbsDiff(String S, int N, int K) { int zeros = 0, ones = 0; for ( int i = 0; i < N; ++i) { if (S[i] == '0' ) ++zeros; else ++ones; } double diff = Math.Abs(ones - zeros); int ans = ( int )Math.Ceiling(diff / K); return ans; } static public void Main() { // Code int N = 7; int K = 5; String S = "1010100" ; // Function Call int ans = minAbsDiff(S, N, K); Console.WriteLine(ans); } } // This code is contributed by lokeshmvs21. |
Javascript
// JavaScript code to implement the approach function minAbsDiff(S, N, K) { let zeros = 0, ones = 0; for (let i = 0; i < N; ++i) { if (S[i] == "0" ) ++zeros; else ++ones; } let diff = Math.abs(ones - zeros); let ans = (diff + K - 1) / K; return ans; } let N = 7; let K = 5; let S = "1010100" ; // Function Call let ans = minAbsDiff(S, N, K); console.log(ans); // This code is contributed by ishankhandelwals. |
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us