Dada una string binaria str de tamaño N y un entero positivo K , la tarea es encontrar el número mínimo de vueltas requeridas para hacer que todas las substrings de tamaño K contengan al menos un ‘1’.
Ejemplos:
Entrada: str = “0001”, K = 2
Salida: 1
Explicación:
Cambiar el bit en el índice 1 modifica str a “0101”.
Todas las substrings de tamaño 2 son «01», «10» y «01».
Cada substring contiene al menos un 1.
Entrada: str = “101”, K = 2
Salida: 0
Explicación:
Todas las substrings de tamaño 2 son “10” y “01”.
Dado que ambos ya tienen al menos un ‘1’, no se requieren cambios en la string original.
Enfoque:
siga los pasos a continuación para resolver el problema:
- La idea es utilizar la técnica de ventana deslizante para verificar si cada substring de longitud K contiene algún ‘1’ o no.
- Mantenga una variable last_idx para almacenar el último índice de una ventana donde el carácter era ‘1’. El valor de esta variable será -1 si no hay un ‘1’ presente en la ventana actual.
- Para cualquier ventana de este tipo, incrementaremos el número de vueltas cambiando el carácter en el último índice de la ventana actual a ‘1’ y actualizando el índice last_idx a ese índice.
- Voltear el último carácter de la ventana actual asegura que las siguientes ventanas K-1 también tendrán al menos un ‘1’. Por lo tanto, este enfoque minimiza el número de vueltas requeridas.
- Repita este proceso para el resto de la string e imprima el conteo final de vueltas requeridas.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the
// minimum numbers of flips
// required in a binary string
// such that all substrings of
// size K has atleast one 1
#include <bits/stdc++.h>
using namespace std;
// Function to calculate and
// return the minimum number
// of flips to make string valid
int minimumMoves(string S, int K)
{
int N = S.length();
// Stores the count
// of required flips
int ops = 0;
// Stores the last index
// of '1' in the string
int last_idx = -1;
// Check for the first
// substring of length K
for (int i = 0; i < K; i++) {
// If i-th character
// is '1'
if (S[i] == '1')
last_idx = i;
}
// If the substring had
// no '1'
if (last_idx == -1) {
// Increase the
// count of required
// flips
++ops;
// Flip the last
// index of the
// window
S[K - 1] = '1';
// Update the last
// index which
// contains 1
last_idx = K - 1;
}
// Check for remaining substrings
for (int i = 1; i < N - K + 1; i++) {
// If last_idx does not
// belong to current
// window make it -1
if (last_idx < i)
last_idx = -1;
// If the last character of
// the current substring
// is '1', then update
// last_idx to i+k-1;
if (S[i + K - 1] == '1')
last_idx = i + K - 1;
// If last_idx == -1, then
// the current substring
// has no 1
if (last_idx == -1) {
// Increase the count
// of flips
++ops;
// Update the last
// index of the
// current window
S[i + K - 1] = '1';
// Store the last
// index of current
// window as the
// index of last '1'
// in the string
last_idx = i + K - 1;
}
}
// Return the number
// of operations
return ops;
}
// Driver Code
int main()
{
string S = "001010000";
int K = 3;
cout << minimumMoves(S, K);
return 0;
}
Java
// Java program to find the
// minimum numbers of flips
// required in a binary string
// such that all substrings of
// size K has atleast one 1
class GFG{
// Function to calculate and
// return the minimum number
// of flips to make string valid
public static int minimumMoves(String s, int K)
{
StringBuilder S = new StringBuilder(s);
int N = S.length();
// Stores the count
// of required flips
int ops = 0;
// Stores the last index
// of '1' in the string
int last_idx = -1;
// Check for the first
// substring of length K
for(int i = 0; i < K; i++)
{
// If i-th character
// is '1'
if (S.charAt(i) == '1')
last_idx = i;
}
// If the substring had
// no '1'
if (last_idx == -1)
{
// Increase the count
// of required flips
++ops;
// Flip the last index
// of the window
S.setCharAt(K - 1, '1');
// Update the last index
// which contains 1
last_idx = K - 1;
}
// Check for remaining substrings
for(int i = 1; i < N - K + 1; i++)
{
// If last_idx does not
// belong to current
// window make it -1
if (last_idx < i)
last_idx = -1;
// If the last character of
// the current substring
// is '1', then update
// last_idx to i+k-1;
if (S.charAt(i + K - 1) == '1')
last_idx = i + K - 1;
// If last_idx == -1, then
// the current substring
// has no 1
if (last_idx == -1)
{
// Increase the count
// of flips
++ops;
// Update the last index
// of the current window
S.setCharAt(i + K - 1, '1');
// Store the last index
// of current window as
// the index of last '1'
// in the string
last_idx = i + K - 1;
}
}
// Return the number
// of operations
return ops;
}
// Driver Code
public static void main(String[] args)
{
String S = "001010000";
int K = 3;
System.out.println(minimumMoves(S, K));
}
}
// This code is contributed by jrishabh99
Python3
# Python3 program to find the minimum # numbers of flips required in a binary # string such that all substrings of # size K has atleast one 1 # Function to calculate and # return the minimum number # of flips to make string valid def minimumMoves(S, K): N = len(S) # Stores the count # of required flips ops = 0 # Stores the last index # of '1' in the string last_idx = -1 # Check for the first # substring of length K for i in range(K): # If i-th character # is '1' if (S[i] == '1'): last_idx = i # If the substring had # no '1' if (last_idx == -1): # Increase the count # of required flips ops += 1 # Flip the last index # of the window S[K - 1] = '1' # Update the last index # which contains 1 last_idx = K - 1 # Check for remaining substrings for i in range(N - K + 1): # If last_idx does not # belong to current # window make it -1 if (last_idx < i): last_idx = -1 # If the last character of # the current substring # is '1', then update # last_idx to i + k-1; if (S[i + K - 1] == '1'): last_idx = i + K - 1 # If last_idx == -1, then # the current substring # has no 1 if (last_idx == -1): # Increase the count # of flips ops += 1 # Update the last index # of the current window S = S[:i + K - 1] + '1' + S[i + K:] # Store the last index of # current window as the index # of last '1' in the string last_idx = i + K - 1 # Return the number # of operations return ops # Driver Code S = "001010000" K = 3; print(minimumMoves(S, K)) # This code is contributed by yatinagg
C#
// C# program to find the
// minimum numbers of flips
// required in a binary string
// such that all substrings of
// size K has atleast one 1
using System;
using System.Text;
class GFG{
// Function to calculate and
// return the minimum number
// of flips to make string valid
public static int minimumMoves(String s, int K)
{
StringBuilder S = new StringBuilder(s);
int N = S.Length;
// Stores the count
// of required flips
int ops = 0;
// Stores the last index
// of '1' in the string
int last_idx = -1;
// Check for the first
// substring of length K
for(int i = 0; i < K; i++)
{
// If i-th character
// is '1'
if (S[i] == '1')
last_idx = i;
}
// If the substring had
// no '1'
if (last_idx == -1)
{
// Increase the count
// of required flips
++ops;
// Flip the last index
// of the window
S.Insert(K - 1, '1');
// Update the last index
// which contains 1
last_idx = K - 1;
}
// Check for remaining substrings
for(int i = 1; i < N - K + 1; i++)
{
// If last_idx does not
// belong to current
// window make it -1
if (last_idx < i)
last_idx = -1;
// If the last character of
// the current substring
// is '1', then update
// last_idx to i+k-1;
if (S[i + K - 1] == '1')
last_idx = i + K - 1;
// If last_idx == -1, then
// the current substring
// has no 1
if (last_idx == -1)
{
// Increase the count
// of flips
++ops;
// Update the last index
// of the current window
S.Insert(i + K - 1, '1');
// Store the last index
// of current window as
// the index of last '1'
// in the string
last_idx = i + K - 1;
}
}
// Return the number
// of operations
return ops;
}
// Driver Code
public static void Main(String[] args)
{
String S = "001010000";
int K = 3;
Console.WriteLine(minimumMoves(S, K));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript program to find the
// minimum numbers of flips
// required in a binary string
// such that all substrings of
// size K has atleast one 1
// Function to calculate and
// return the minimum number
// of flips to make string valid
function minimumMoves(S, K)
{
var N = S.length;
// Stores the count
// of required flips
var ops = 0;
// Stores the last index
// of '1' in the string
var last_idx = -1;
// Check for the first
// substring of length K
for (var i = 0; i < K; i++) {
// If i-th character
// is '1'
if (S[i] == '1')
last_idx = i;
}
// If the substring had
// no '1'
if (last_idx == -1) {
// Increase the
// count of required
// flips
++ops;
// Flip the last
// index of the
// window
S[K - 1] = '1';
// Update the last
// index which
// contains 1
last_idx = K - 1;
}
// Check for remaining substrings
for (var i = 1; i < N - K + 1; i++) {
// If last_idx does not
// belong to current
// window make it -1
if (last_idx < i)
last_idx = -1;
// If the last character of
// the current substring
// is '1', then update
// last_idx to i+k-1;
if (S[i + K - 1] == '1')
last_idx = i + K - 1;
// If last_idx == -1, then
// the current substring
// has no 1
if (last_idx == -1) {
// Increase the count
// of flips
++ops;
// Update the last
// index of the
// current window
S[i + K - 1] = '1';
// Store the last
// index of current
// window as the
// index of last '1'
// in the string
last_idx = i + K - 1;
}
}
// Return the number
// of operations
return ops;
}
// Driver Code
var S = "001010000";
var K = 3;
document.write( minimumMoves(S, K));
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por sri_srajit y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA