Dada una string binaria S de longitud N . Distribuya los 0 y los 1 de la string en K grupos de manera que:
- Cada grupo consta al menos de un personaje.
- Ningún grupo contiene tanto el 1 como el 0.
- Todos los 1 y 0 de la string se distribuyen entre todos los grupos.
La tarea es distribuir todos los caracteres de tal manera que se maximice el número mínimo de caracteres en cualquier grupo e imprimir ese número de caracteres (es decir, el número mínimo de caracteres en cualquier grupo entre los K grupos).
Ejemplos:
Entrada: S = “01011”, K=5
Salida: 1
Explicación: los K grupos serían – {0}, {0}, {1}, {1}, {1}Entrada: S = “11110000000111111”, K=4
Salida: 3
Enfoque: el problema se puede resolver fácilmente mediante una técnica codiciosa .
Tomaremos iterativamente cada caso en consideración, es decir
- para cada i, de 1 a K-1,
- asignaremos i grupos para almacenar todos los ceros y
- Grupos K- i para almacenar todos los unos.
- En cada iteración, seguiremos tomando el máximo de la respuesta actual.
Se puede seguir el siguiente enfoque para llegar a la respuesta:
- Calcula el número de 0s y 1s en la string.
- Inicializar respuesta por 0.
- Si K>N (donde N es la longitud de la string), devuelva 0, ya que en este caso no es posible hacer K grupos de modo que cada uno de ellos contenga al menos un carácter.
- Iterar desde i =1 hasta i =K-1. En cada iteración, asigne grupos i para almacenar todos los ceros y grupos K- i para almacenar todos los unos.
- Encuentre el número de ceros en cada uno de los i grupos dividiendo el número total de 0 por el número de grupos asignados para almacenar los 0 (supongamos que quedan algunos ceros, ya que es posible que no se distribuyan por igual en todos los grupos, entonces se pueden poner en cualquier grupo. No importa, ya que necesitamos el grupo con un mínimo de caracteres). Del mismo modo, encuentre el número de 1 en cada grupo.
- Encuentre el mínimo de ambos (es decir, 0 en un grupo y 1 en un grupo) y guárdelo en una variable, digamos min_count.
- Encuentre el máximo de todos los min_count en cada iteración y devuélvalo.
A continuación se muestra el código basado en el enfoque anterior:
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 groups
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 = 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 Code
int main()
{
string S = "11110000000111111";
int K = 4;
int ans = divideString(S, K);
cout << ans;
}
Java
// Java program of the above approach
import 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 groups def 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 answer S = '11110000000111111' K = 4 ans = divideString(S, K) print(ans) '''This code is contributed by Rajat Kumar (GLA University).'''
C#
// C# program of the above approach
using 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>
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kamabokogonpachiro y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA