Dada una string binaria S y un entero K , la tarea es encontrar el número mínimo de vueltas requeridas para convertir la string dada en una concatenación de substrings iguales de longitud K. Se da que la string dada se puede dividir en substrings de longitud K.
Ejemplos:
Entrada: S = “101100101”, K = 3
Salida: 1
Explicación:
Cambie el ‘0’ del índice 5 al ‘1’.
La string resultante es S = «101101101».
Es la concatenación de la substring “101”.
Por lo tanto, el número mínimo de lanzamientos requeridos es 1.Entrada: S = “10110111”, K = 4
Salida: 2
Explicación:
Cambia el ‘0’ y el ‘1’ en los índices 4 y 5 respectivamente.
La string resultante es S = «10111011».
Es la concatenación de la substring “1011”.
Por lo tanto, el número mínimo de lanzamientos requeridos es 2.
Enfoque:
el problema se puede resolver utilizando el enfoque codicioso .
Siga los pasos a continuación:
- Iterar la string dada con incrementos de K índices de cada índice y llevar la cuenta de los 0 y los 1 .
- El caracter que ocurre el número mínimo de veces debe ser volteado y seguir incrementando ese conteo .
- Realice los pasos anteriores para todos los índices de 0 a K-1 para obtener el número mínimo de lanzamientos necesarios.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns the minimum
// number of flips to convert
// the s into a concatenation
// of K-length sub-string
int minOperations(string S, int K)
{
// Stores the result
int ans = 0;
// Iterate through string index
for (int i = 0; i < K; i++) {
// Stores count of 0s & 1s
int zero = 0, one = 0;
// Iterate making K jumps
for (int j = i;
j < S.size(); j += K) {
// Count 0's
if (S[j] == '0')
zero++;
// Count 1's
else
one++;
}
// Add minimum flips
// for index i
ans += min(zero, one);
}
// Return minimum number
// of flips
return ans;
}
// Driver Code
int main()
{
string S = "110100101";
int K = 3;
cout << minOperations(S, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.io.*;
class GFG{
// Function that returns the minimum
// number of flips to convert
// the s into a concatenation
// of K-length sub-string
public static int minOperations(String S, int K)
{
// Stores the result
int ans = 0;
// Iterate through string index
for(int i = 0; i < K; i++)
{
// Stores count of 0s & 1s
int zero = 0, one = 0;
// Iterate making K jumps
for(int j = i; j < S.length(); j += K)
{
// Count 0's
if (S.charAt(j) == '0')
zero++;
// Count 1's
else
one++;
}
// Add minimum flips
// for index i
ans += Math.min(zero, one);
}
// Return minimum number
// of flips
return ans;
}
// Driver Code
public static void main(String args[])
{
String S = "110100101";
int K = 3;
System.out.println(minOperations(S, K));
}
}
// This code is contributed by grand_master
Python3
# Python3 program to implement # the above approach # Function that returns the minimum # number of flips to convert the s # into a concatenation of K-length # sub-string def minOperations(S, K): # Stores the result ans = 0 # Iterate through string index for i in range(K): # Stores count of 0s & 1s zero, one = 0, 0 # Iterate making K jumps for j in range(i, len(S), K): # Count 0's if(S[j] == '0'): zero += 1 # Count 1's else: one += 1 # Add minimum flips # for index i ans += min(zero, one) # Return minimum number # of flips return ans # Driver code if __name__ == '__main__': s = "110100101" K = 3 print(minOperations(s, K)) # This code is contributed by Shivam Singh
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Function that returns the minimum
// number of flips to convert
// the s into a concatenation
// of K-length sub-string
public static int minOperations(String S, int K)
{
// Stores the result
int ans = 0;
// Iterate through string index
for(int i = 0; i < K; i++)
{
// Stores count of 0s & 1s
int zero = 0, one = 0;
// Iterate making K jumps
for(int j = i; j < S.Length; j += K)
{
// Count 0's
if (S[j] == '0')
zero++;
// Count 1's
else
one++;
}
// Add minimum flips
// for index i
ans += Math.Min(zero, one);
}
// Return minimum number
// of flips
return ans;
}
// Driver Code
public static void Main(String []args)
{
String S = "110100101";
int K = 3;
Console.WriteLine(minOperations(S, K));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript program to implement
// the above approach
// Function that returns the minimum
// number of flips to convert
// the s into a concatenation
// of K-length sub-string
function minOperations(S, K) {
// Stores the result
var ans = 0;
// Iterate through string index
for (var i = 0; i < K; i++) {
// Stores count of 0s & 1s
var zero = 0,
one = 0;
// Iterate making K jumps
for (var j = i; j < S.length; j += K) {
// Count 0's
if (S[j] === "0")
zero++;
// Count 1's
else
one++;
}
// Add minimum flips
// for index i
ans += Math.min(zero, one);
}
// Return minimum number
// of flips
return ans;
}
// Driver Code
var S = "110100101";
var K = 3;
document.write(minOperations(S, K));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(1)