Given a binary string S of length N. Distribute 0s and 1s of the string into K groups such that:
- Each group consists atleast a character.
- No group contains both 1 and 0.
- All 1s and 0s of the string are distributed among all the groups.
The task is to distribute all the characters in such a way that minimum number of characters in any group is maximized and print that number of characters (i.e. minimum number of characters in any group among the K groups).
Examples:
Input: S = “01011”, K=5
Output: 1
Explanation: the K groups would be – {0}, {0}, {1}, {1}, {1}Input: S = “11110000000111111”, K=4
Output: 3
Approach: The problem can be easily solved by greedy technique.
We will iteratively take each case into consideration i.e.
- for each i, from 1 to K-1,
- we will assign i groups to store all the zeroes and
- K-i groups to store all the ones.
- At each iteration, we will keep taking maximum of the current answer.
The following approach can be followed to arrive at the answer:
- Calculate the number of 0s and 1s in the string.
- Initialize answer by 0.
- If K>N (where N is length of string), return 0, as in this case it is not possible to make K groups such that each of them contains atleast one character.
- Iterate from i=1 to i=K-1. At each iteration, assign i groups to store all the zeroes and K-i groups to store all the ones.
- Find number of zeroes in each of the i groups by dividing total number of 0s by the number of groups assigned to store the 0s (suppose some zeroes are left, as they may not be distributed equally to all the groups, then they can be put into any one group. It doesn’t matter, as we need the group with minimum characters). Similarly, find number of 1s in each group.
- Find minimum of both (i.e. 0s in a group and 1s in a group) and store in a variable, say min_count.
- Find maximum of all min_count in each iteration and return that.
Below is the code based on above approach:
C++
// C++ code for Divide the binary string// into K groups such that minimum number// of characters in any group is maximized#include <bits/stdc++.h>using namespace std;// Function to find the maximized minimum// number of characters in a group,// when given string is divided into// K groupsint divideString(string S, int K){ // calculating length of given string int N = S.length(); int zero = 0, one = 0; // Calculating number of 0s and 1s // in given string for (int i = 0; i < N; i++) { if (S[i] == '0') { zero++; } else { one++; } } // initializing answer by 0 int answer = 0; // if K>size of string, then it is not // possible to make K groups such that // each of them contains atleast 1 character if (K > N) { return 0; } for (int i = 1; i < K; i++) { // let there be i groups with // all elements 0 int zero_groups = i; int one_groups = K - i; // so, there will be K-i groups with // all elements 1 int count0 = zero / zero_groups; // number of 0s in // each zero_groups int count1 = one / one_groups; // number of 1s in // each one_groups int min_count = min(count0, count1); // since we have to find the // count of characters in group // with minimum characters answer = max(answer, min_count); // since we have to // maximize the answer } // returning answer return answer;}// Driver Codeint main(){ string S = "11110000000111111"; int K = 4; int ans = divideString(S, K); cout << ans;} |
Java
// Java program of the above approachimport java.io.*;class GFG { // Function to find the maximized minimum // number of characters in a group, // when given string is divided into // K groups static int divideString(String S, int K) { // calculating length of given string int N = S.length(); int zero = 0, one = 0; // Calculating number of 0s and 1s // in given string for (int i = 0; i < N; i++) { if (S.charAt(i) == '0') { zero++; } else { one++; } } // initializing answer by 0 int answer = 0; // if K>size of string, then it is not // possible to make K groups such that // each of them contains atleast 1 character if (K > N) { return 0; } for (int i = 1; i < K; i++) { // let there be i groups with // all elements 0 int zero_groups = i; int one_groups = K - i; // so, there will be K-i groups with // all elements 1 int count0 = zero / zero_groups; // number of 0s in // each zero_groups int count1 = one / one_groups; // number of 1s in // each one_groups int min_count = Math.min(count0, count1); // since we have to find the // count of characters in group // with minimum characters answer = Math.max(answer, min_count); // since we have to // maximize the answer } // returning answer return answer; } // Driver Code public static void main (String[] args) { String S = "11110000000111111"; int K = 4; int ans = divideString(S, K); System.out.println(ans); }}// This code is contributed by hrithikgarg03188. |
Python3
'''Python code for Divide the binary string into K groups such that minimum number of characters in any group is maximized''' # Function to find the maximized minimum# number of characters in a group,# when given string is divided into# K groupsdef divideString(S, K): # calculating length of given string N = len(S) zero, one = 0, 0 # Calculating number of 0s and 1s in given string for i in range(0, N): if S[i] == '0': zero += 1 else: one += 1 # initializing answer by 0 answer = 0 # if K>size of string, then it is not # possible to make K groups such that # each of them contains atleast 1 character if K > N: return 0 # let there be i groups with all elements 0 for i in range(1, K): zero_groups = i one_groups = K - i # so, there will be K-i groups with all elements 1 count0 = zero//zero_groups # number of 0s in each zero_groups count1 = one//one_groups # number of 1s in each one_groups min_count = min(count0, count1) # since we have to find the count of # characters in group with minimum characters answer = max(answer, min_count) # since we have to maximize the answer return answerS = '11110000000111111'K = 4ans = divideString(S, K)print(ans)'''This code is contributed by Rajat Kumar (GLA University).''' |
C#
// C# program of the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to find the maximized minimum // number of characters in a group, // when given string is divided into // K groups static int divideString(string S, int K) { // calculating length of given string int N = S.Length; int zero = 0, one = 0; // Calculating number of 0s and 1s // in given string for (int i = 0; i < N; i++) { if (S[i] == '0') { zero++; } else { one++; } } // initializing answer by 0 int answer = 0; // if K>size of string, then it is not // possible to make K groups such that // each of them contains atleast 1 character if (K > N) { return 0; } for (int i = 1; i < K; i++) { // let there be i groups with // all elements 0 int zero_groups = i; int one_groups = K - i; // so, there will be K-i groups with // all elements 1 int count0 = zero / zero_groups; // number of 0s in // each zero_groups int count1 = one / one_groups; // number of 1s in // each one_groups int min_count = Math.Min(count0, count1); // since we have to find the // count of characters in group // with minimum characters answer = Math.Max(answer, min_count); // since we have to // maximize the answer } // returning answer return answer; } // Driver Code public static void Main(String[] args) { string S = "11110000000111111"; int K = 4; int ans = divideString(S, K); Console.Write(ans); }}// This code is contributed by sanjoy_62. |
Javascript
<script> // JavaScript code for Divide the binary string // into K groups such that minimum number // of characters in any group is maximized // Function to find the maximized minimum // number of characters in a group, // when given string is divided into // K groups const divideString = (S, K) => { // calculating length of given string let N = S.length; let zero = 0, one = 0; // Calculating number of 0s and 1s // in given string for (let i = 0; i < N; i++) { if (S[i] == '0') { zero++; } else { one++; } } // initializing answer by 0 let answer = 0; // if K>size of string, then it is not // possible to make K groups such that // each of them contains atleast 1 character if (K > N) { return 0; } for (let i = 1; i < K; i++) { // let there be i groups with // all elements 0 let zero_groups = i; let one_groups = K - i; // so, there will be K-i groups with // all elements 1 let count0 = parseInt(zero / zero_groups); // number of 0s in // each zero_groups let count1 = parseInt(one / one_groups); // number of 1s in // each one_groups let min_count = Math.min(count0, count1); // since we have to find the // count of characters in group // with minimum characters answer = Math.max(answer, min_count); // since we have to // maximize the answer } // returning answer return answer; } // Driver Code let S = "11110000000111111"; let K = 4; let ans = divideString(S, K); document.write(ans);// This code is contributed by rakeshsahni</script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach:
- Count the number of ‘1’ and ‘0’ characters in the input string “S”.
- Determine the maximum count among the ‘1’s and ‘0’s.
- Calculate the minimum number of characters in any group by dividing the maximum count by “K” and rounding up to the nearest integer.
- Return the minimum number of characters as the output.
Below is the implementation of the above approach:
C++
#include <iostream>#include <vector>#include <algorithm>int distributeCharacters(std::string S, int K) { // Count the number of '1' and '0' characters in the string int count_1 = std::count(S.begin(), S.end(), '1'); int count_0 = std::count(S.begin(), S.end(), '0'); // Find the maximum count among '1' and '0' characters int max_characters = std::max(count_1, count_0); // Calculate the minimum number of characters in any group int min_characters = std::max(1, (max_characters + K - 1) / K); // Return the minimum number of characters return min_characters;}int main() { std::string S = "11110000000111111"; int K = 4; // Call the distributeCharacters function and store the result int result = distributeCharacters(S, K); // Print the result std::cout << result << std::endl; return 0;} |
Java
public class GFG { public static int distributeCharacters(String S, int K) { // Count the number of '1' and '0' characters in the string int count_1 = S.split("1", -1).length - 1; int count_0 = S.split("0", -1).length - 1; // Find the maximum count among '1' and '0' characters int max_characters = Math.max(count_1, count_0); // Calculate the minimum number of characters in any group int min_characters = Math.max(1, (int) Math.floor((max_characters + K - 1) / K)); // Return the minimum number of characters return min_characters; } public static void main(String[] args) { String S = "11110000000111111"; int K = 4; // Call the distributeCharacters function and store the result int result = distributeCharacters(S, K); // Print the result System.out.println(result); }} |
Python3
def distribute_characters(S, K): # Count the number of '1' and '0' characters in the string count_1 = S.count('1') count_0 = S.count('0') # Find the maximum count among '1' and '0' characters max_characters = max(count_1, count_0) # Calculate the minimum number of characters in any group min_characters = max(1, (max_characters + K - 1) // K) # Return the minimum number of characters return min_charactersdef main(): S = "11110000000111111" K = 4 # Call the distribute_characters function and store the result result = distribute_characters(S, K) # Print the result print(result)if __name__ == '__main__': main() |
C#
using System;class GFG { static int DistributeCharacters(string S, int K) { // Count the number of '1' and '0' characters in the // string int count_1 = CountOccurrences(S, '1'); int count_0 = CountOccurrences(S, '0'); // Find the maximum count among '1' and '0' // characters int max_characters = Math.Max(count_1, count_0); // Calculate the minimum number of characters in any // group int min_characters = Math.Max(1, (max_characters + K - 1) / K); // Return the minimum number of characters return min_characters; } static int CountOccurrences(string str, char c) { int count = 0; foreach(char ch in str) { if (ch == c) { count++; } } return count; } static void Main(string[] args) { string S = "11110000000111111"; int K = 4; // Call the DistributeCharacters function and store // the result int result = DistributeCharacters(S, K); // Print the result Console.WriteLine(result); }} |
Javascript
// JavaScript code of the above approachfunction distributeCharacters(S, K) { // Count the number of '1' and '0' characters in the string const count_1 = S.split('1').length - 1; const count_0 = S.split('0').length - 1; // Find the maximum count among '1' and '0' characters const max_characters = Math.max(count_1, count_0); // Calculate the minimum number of characters in any group const min_characters = Math.max(1, Math.ceil(max_characters / K)); // Return the minimum number of characters return min_characters;}const S = "11110000000111111";const K = 4;// Call the distributeCharacters function and store the resultconst result = distributeCharacters(S, K);// Print the resultconsole.log(result);// This code is contributed by Susobhan Akhuli |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
