Minimice las operaciones para hacer que la string binaria dada sea solo 1 al convertir repetidamente K caracteres consecutivos en 1

Dada una string binaria str de N caracteres y un número entero K , la tarea es encontrar los movimientos mínimos necesarios para convertir todos los caracteres de la string en 1, donde en cada movimiento, K caracteres consecutivos se pueden convertir en 1 .

Ejemplo:

Entrada: str=”0010″, K=3
Salida: 2
Explicación:
Mover 1: Seleccione la substring de 0 a 2 y reemplácela con todo 1.
Mover 2: Seleccione la substring de 1 a 3 y reemplácela con todo 1.

Entrada: str=”0000010″, K=1
Salida: 6

Enfoque: este problema se puede resolver utilizando un enfoque codicioso . Para resolver este problema, siga los siguientes pasos:

1. Cree una variable cnt para almacenar el número mínimo de movimientos necesarios. Inicializarlo con 0 .
2. Recorra la string usando una variable i y str[i] = ‘0’ , luego actualice i a i + K y aumente cnt en 1 , porque no importa cuáles sean estos caracteres, siempre se requiere un movimiento para convertir el carácter str[i ] a ‘1’ .
3. Después de que finalice el ciclo, devuelva cnt , que será la respuesta requerida.

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

// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// operations required to convert
// the binary string str to all 1s
int minMoves(string str, int K)
{
    int N = str.size();
 
    // Variable to store number
    // of minimum moves required
    int cnt = 0;
 
    int i = 0;
 
    // Loop to traverse str
    while (i < N) {
 
        // If element is '0'
        if (str[i] == '0') {
            i += K;
            cnt += 1;
        }
 
        // If element is '1'
        else {
            i++;
        }
    }
 
    return cnt;
}
 
// Driver Code
int main()
{
    string str = "0010";
    int K = 3;
    cout << minMoves(str, K);
}

// Java code for the above approach
class GFG {
 
    // Function to find the minimum
    // operations required to convert
    // the binary String str to all 1s
    static int minMoves(String str, int K) {
        int N = str.length();
 
        // Variable to store number
        // of minimum moves required
        int cnt = 0;
 
        int i = 0;
 
        // Loop to traverse str
        while (i < N) {
 
            // If element is '0'
            if (str.charAt(i) == '0') {
                i += K;
                cnt += 1;
            }
 
            // If element is '1'
            else {
                i++;
            }
        }
 
        return cnt;
    }
 
    // Driver Code
    public static void main(String args[]) {
        String str = "0010";
        int K = 3;
        System.out.println(minMoves(str, K));
    }
}
 
// This code is contributed by Saurabh Jaiswal

# Python code for the above approach
 
# Function to find the minimum
# operations required to convert
# the binary string str to all 1s
def minMoves(str, K):
    N = len(str)
 
    # Variable to store number
    # of minimum moves required
    cnt = 0
 
    i = 0
 
    # Loop to traverse str
    while (i < N):
 
        # If element is '0'
        if (str[i] == '0'):
            i += K
            cnt += 1
        # If element is '1'
        else:
            i += 1
 
    return cnt
 
# Driver Code
str = "0010"
K = 3
print(minMoves(str, K))
 
# This code is contributed by Saurabh Jaiswal

// C# code for the above approach
using System;
 
class GFG
{
   
// Function to find the minimum
// operations required to convert
// the binary string str to all 1s
static int minMoves(string str, int K)
{
    int N = str.Length;
 
    // Variable to store number
    // of minimum moves required
    int cnt = 0;
 
    int i = 0;
 
    // Loop to traverse str
    while (i < N) {
 
        // If element is '0'
        if (str[i] == '0') {
            i += K;
            cnt += 1;
        }
 
        // If element is '1'
        else {
            i++;
        }
    }
 
    return cnt;
}
 
// Driver Code
public static void Main()
{
    string str = "0010";
    int K = 3;
    Console.Write(minMoves(str, K));
}
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
       // JavaScript code for the above approach
 
 
       // Function to find the minimum
       // operations required to convert
       // the binary string str to all 1s
       function minMoves(str, K) {
           let N = str.length;
 
           // Variable to store number
           // of minimum moves required
           let cnt = 0;
 
           let i = 0;
 
           // Loop to traverse str
           while (i < N) {
 
               // If element is '0'
               if (str[i] == '0') {
                   i += K;
                   cnt += 1;
               }
 
               // If element is '1'
               else {
                   i++;
               }
           }
 
           return cnt;
       }
 
       // Driver Code
 
       let str = "0010";
       let K = 3;
       document.write(minMoves(str, K));
 
 // This code is contributed by Potta Lokesh
   </script>

2

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