Minimice los giros para hacer que la string binaria sea solo 1 al voltear los caracteres en la substring de tamaño K repetidamente

Dada una string binaria S de tamaño N y un entero K , la tarea es encontrar el número mínimo de operaciones requeridas para convertir todos los caracteres en 1 en la string binaria al invertir los caracteres en la substring de tamaño K . Si no es posible hacerlo, imprima “-1” .

Ejemplos:

Entrada: S = “00010110”, K = 3
Salida: 3
Explicación:
A continuación se muestran las operaciones realizadas:

1. Considere la substring S[0, 2] que es de tamaño K(= 3) y cambiando esos caracteres modifica la string a «11110110».
2. Considere la substring S[4, 6] que es de tamaño K(= 3) y cambiando esos caracteres modifica la string a «11111000».
3. Considere la substring S[5, 7] que es de tamaño K(= 3) y cambiando esos caracteres modifica la string a «11111111».

Después de las operaciones anteriores, todos los 0 se convierten en 1 y el número mínimo de operaciones requeridas es 3.

Entrada: S = “01010”, K = 4
Salida: -1

Enfoque: el problema dado se puede resolver utilizando el enfoque codicioso . Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos minOperations como 0 que almacena el conteo del número mínimo de operaciones requeridas.
• Recorra la string S usando la variable i y si los caracteres S[i] son ​​’0′ y el valor de (i + K) es como máximo K , entonces invierta todos los caracteres de la substring S[i, i + K] e incrementa el valor de minOperations en 1 .
• Después de las operaciones anteriores, recorra la string S y, si existe algún carácter ‘0’ , imprima «-1» y salga del bucle .
• Si todos los caracteres de la string S son 1 , imprima minOperations como el número mínimo de operaciones resultante.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum number
// of operations required to convert all
// the characters to 1 by flipping the
// substrings of size K
void minOperation(string S, int K, int N)
{
 
    // Stores the minimum number of
    // operations required
    int min = 0;
 
    int i;
 
    // Traverse the string S
    for (i = 0; i < N; i++) {
 
        // If the character is 0
        if (S[i] == '0' && i + K <= N) {
 
            // Flip the substrings of
            // size K starting from i
            for (int j = i; j < i + K; j++) {
                if (S[j] == '1')
                    S[j] = '0';
                else
                    S[j] = '1';
            }
 
            // Increment the minimum count
            // of operations required
            min++;
        }
    }
 
    // After performing the operations
    // check if string S contains any 0s
    for (i = 0; i < N; i++) {
        if (S[i] == '0')
            break;
    }
 
    // If S contains only 1's
    if (i == N)
        cout << min;
    else
        cout << -1;
}
 
// Driver Code
int main()
{
 
    string S = "00010110";
    int K = 3;
    int N = S.length();
    minOperation(S, K, N);
 
    return 0;
}

// Java program for the above approach
public class GFG
{
 
// Function to find the minimum number
// of operations required to convert all
// the characters to 1 by flipping the
// substrings of size K
static void minOperation(String S, int K, int N)
{
 
    // Stores the minimum number of
    // operations required
    int min = 0;
 
    int i;
 
    // Traverse the string S
    for (i = 0; i < N; i++) {
 
        // If the character is 0
        if (S.charAt(i) == '0' && i + K <= N) {
 
            // Flip the substrings of
            // size K starting from i
            for (int j = i; j < i + K; j++) {
                if (S.charAt(j) == '1')
                    S = S.substring(0, j) + '0' + S.substring(j + 1);
                else
                   S = S.substring(0, j) + '1' + S.substring(j + 1);
            }
 
            // Increment the minimum count
            // of operations required
            min++;
        }
    }
 
    // After performing the operations
    // check if string S contains any 0s
    for (i = 0; i < N; i++) {
        if (S.charAt(i) == '0')
            break;
    }
 
    // If S contains only 1's
    if (i == N)
      System.out.println(min);
    else
      System.out.println(-1);
}
 
// Driver Code
public static void main(String []args)
{
 
    String S = "00010110";
    int K = 3;
    int N = S.length();
    minOperation(S, K, N);
}
}
 
// This code is contributed by AnkThon

# Function to find the minimum number
# of operations required to convert all
# the characters to 1 by flipping the
# substrings of size K
def minOperation(St, K, N):
    S = list(St)
 
    # Stores the minimum number of
    # operations required
    min = 0
 
    i = 0
 
    # Traverse the string S
    for i in range(0, N):
 
        # If the character is 0
        if (S[i] == '0' and i + K <= N):
 
            # Flip the substrings of
            # size K starting from i
            j = i
            while(j < i + K):
                if (S[j] == '1'):
                    S[j] = '0'
                else:
                    S[j] = '1'
                j += 1
 
            # Increment the minimum count
            # of operations required
            min += 1
 
    # After performing the operations
    # check if string S contains any 0s
    temp = 0
 
    for i in range(0, N):
        temp += 1
        if (S[i] == '0'):
            break
 
    # If S contains only 1's
    if (temp == N):
        print(min)
    else:
        print(-1)
 
# Driver Code
S = "00010110"
K = 3
N = len(S)
minOperation(S, K, N)
 
# This code is contributed by gfgking

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to find the minimum number
// of operations required to convert all
// the characters to 1 by flipping the
// substrings of size K
static void minOperation(string S, int K, int N)
{
 
    // Stores the minimum number of
    // operations required
    int min = 0;
 
    int i;
 
    // Traverse the string S
    for (i = 0; i < N; i++) {
 
        // If the character is 0
        if (S[i] == '0' && i + K <= N) {
 
            // Flip the substrings of
            // size K starting from i
            for (int j = i; j < i + K; j++) {
                if (S[j] == '1')
                    S = S.Substring(0, j) + '0' + S.Substring(j + 1);
                else
                   S = S.Substring(0, j) + '1' + S.Substring(j + 1);
            }
 
            // Increment the minimum count
            // of operations required
            min++;
        }
    }
 
    // After performing the operations
    // check if string S contains any 0s
    for (i = 0; i < N; i++) {
        if (S[i] == '0')
            break;
    }
 
    // If S contains only 1's
    if (i == N)
      Console.Write(min);
    else
      Console.Write(-1);
}
 
// Driver Code
public static void Main()
{
 
    string S = "00010110";
    int K = 3;
    int N = S.Length;
    minOperation(S, K, N);
}
}
 
// This code is contributed by SURENDRA_GANGWAR.

<script>
 
// Function to find the minimum number
// of operations required to convert all
// the characters to 1 by flipping the
// substrings of size K
function minOperation(St, K, N)
{
    S = St.split('');
 
    // Stores the minimum number of
    // operations required
    let min = 0;
 
    let i;
 
    // Traverse the string S
    for (i = 0; i < N; i++) {
 
        // If the character is 0
        if (S[i] == '0' && i + K <= N) {
 
            // Flip the substrings of
            // size K starting from i
            for (let j = i; j < i + K; j++) {
                if (S[j] == '1')
                    S[j] = '0';
                else
                    S[j] = '1';
            }
 
            // Increment the minimum count
            // of operations required
            min++;
        }
    }
 
    // After performing the operations
    // check if string S contains any 0s
    for (i = 0; i < N; i++) {
        if (S[i] == '0')
            break;
    }
 
    // If S contains only 1's
    if (i == N)
        document.write(min);
    else
        document.write(-1);
}
 
// Driver Code
        let S = "00010110";
    let K = 3;
    let N = S.length;
    minOperation(S, K, N);
 
// This code is contributed by sanjoy_62.   
</script>

3

Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)