Dada una string binaria S de tamaño N y un número K , la tarea es encontrar si todos los ‘0’ se pueden cambiar a ‘ 1′ en cualquier número de operaciones. En una operación, si S[i] es inicialmente ‘1’ , entonces todos los ‘0 ‘ en el rango [i+1, i+K] se pueden cambiar a ‘1’ s, para 0≤i<NK .
Ejemplos:
Entrada: S=”100100″, N=6, K=2
Salida: SÍ
Explicación: S[0] puede usarse para cambiar S[1] y S[2] a 1
s S[3] puede usarse para cambiar S [4] y S[5] en 1sEntrada: S=”110000″, N=6, K=2
Salida: NO
Enfoque ingenuo: el enfoque más simple es recorrer la string de manera inversa y, si se encuentra un ‘0’ , verificar si la posición del ‘1’ más cercano a la izquierda está a más de K índices de distancia. Si es verdadero, escriba «NO» .
Complejidad temporal: O(N*K)
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar una pila . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables flag y cuente como 1 y 0 respectivamente para almacenar el resultado y contar el número de ‘ 0′ que han sido cambiados por la última aparición de ‘ 1′ .
- Inicialice una pila vacía st .
- Atraviese la string S y haga lo siguiente:
- Si la pila está vacía :
- Si el elemento actual es ‘0’ , cambie el indicador a 0 y rompa , ya que este ‘ 0′ no se puede cambiar a ‘1’ .
- De lo contrario, actualice la cuenta a 0 y empuje 1 a st .
- De lo contrario:
- Si el elemento actual es ‘0’, haga lo siguiente:
- Incrementa el conteo en 1.
- Si el conteo se vuelve igual a K , saque la pila st y actualice el conteo a 0
- De lo contrario, actualice el conteo a 0 .
- Si el elemento actual es ‘0’, haga lo siguiente:
- Si la pila está vacía :
- Si el valor de la bandera es 1 , imprima «SÍ» , de lo contrario, imprima «NO» como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check whether all 0s
// in the string can be changed into 1s
void changeCharacters(string S, int N, int K)
{
int flag = 1;
// Store the count of 0s converted
// for the last occurrence of 1
int count = 0;
// Declere a stack
stack<char> st;
// Traverse the string, S
for (int i = 0; i < N; i++) {
// If stack is empty
if (st.empty()) {
// There is no 1 that can
// change this 0 to 1
if (S[i] == '0') {
flag = 0;
break;
}
// Push 1 into the stack
count = 0;
st.push(S[i]);
}
else {
if (S[i] == '0') {
count++;
// The last 1 has reached
// its limit
if (count == K) {
st.pop();
count = 0;
}
}
// New 1 has been found which
// can now change at most K 0s
else {
count = 0;
}
}
}
// If flag is 1, print "YES"
// else print "NO"
if (flag)
cout << "YES" << endl;
else
cout << "NO" << endl;
}
// Driver code
int main()
{
// Given Input
string S = "100100";
int N = S.length();
int K = 2;
// Function call
changeCharacters(S, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check whether all 0s
// in the string can be changed into 1s
static void changeCharacters(String S, int N, int K)
{
int flag = 1;
// Store the count of 0s converted
// for the last occurrence of 1
int count = 0;
// Declere a stack
Stack<Character> st = new Stack<>();
// Traverse the string, S
for(int i = 0; i < N; i++)
{
// If stack is empty
if (st.empty())
{
// There is no 1 that can
// change this 0 to 1
if (S.charAt(i) == '0')
{
flag = 0;
break;
}
// Push 1 into the stack
count = 0;
st.push(S.charAt(i));
}
else
{
if (S.charAt(i) == '0')
{
count++;
// The last 1 has reached
// its limit
if (count == K)
{
st.pop();
count = 0;
}
}
// New 1 has been found which
// can now change at most K 0s
else
{
count = 0;
}
}
}
// If flag is 1, print "YES"
// else print "NO"
if (flag == 1)
System.out.print("YES");
else
System.out.print("NO");
}
// Driver code
public static void main(String args[])
{
// Given Input
String S = "100100";
int N = S.length();
int K = 2;
// Function call
changeCharacters(S, N, K);
}
}
// This code is contributed by ipg2016107
Python3
# Python3 program for the above approach
# Function to check whether all 0s
# in the string can be changed into 1s
def changeCharacters(S, N, K):
flag = 1
# Store the count of 0s converted
# for the last occurrence of 1
count = 0
# Declere a stack
st = []
# Traverse the string, S
for i in range(N):
# If stack is empty
if len(st) == 0:
# There is no 1 that can
# change this 0 to 1
if (S[i] == '0'):
flag = 0
break
# Push 1 into the stack
count = 0
st.append(S[i])
else:
if (S[i] == '0'):
count+=1
# The last 1 has reached
# its limit
if (count == K):
del st[-1]
count = 0
# New 1 has been found which
# can now change at most K 0s
else:
count = 0
# If flag is 1, pr"YES"
# else pr"NO"
if (flag):
print("YES")
else:
print("NO")
# Driver code
if __name__ == '__main__':
# Given Input
S = "100100"
N = len(S)
K = 2
# Function call
changeCharacters(S, N, K)
# This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to check whether all 0s
// in the string can be changed into 1s
static void changeCharacters(string S, int N, int K)
{
int flag = 1;
// Store the count of 0s converted
// for the last occurrence of 1
int count = 0;
// Declere a stack
Stack<char> st = new Stack<char>();
// Traverse the string, S
for(int i = 0; i < N; i++) {
// If stack is empty
if (st.Count==0) {
// There is no 1 that can
// change this 0 to 1
if (S[i] == '0') {
flag = 0;
break;
}
// Push 1 into the stack
count = 0;
st.Push(S[i]);
}
else {
if (S[i] == '0') {
count++;
// The last 1 has reached
// its limit
if (count == K) {
st.Pop();
count = 0;
}
}
// New 1 has been found which
// can now change at most K 0s
else {
count = 0;
}
}
}
// If flag is 1, print "YES"
// else print "NO"
if (flag == 1)
Console.Write("YES");
else
Console.Write("NO");
}
// Driver code
public static void Main()
{
// Given Input
string S = "100100";
int N = S.Length;
int K = 2;
// Function call
changeCharacters(S, N, K);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach
// Function to check whether all 0s
// in the string can be changed into 1s
function changeCharacters(S, N, K) {
let flag = 1;
// Store the count of 0s converted
// for the last occurrence of 1
let count = 0;
// Declere a stack
let st = new Array();
// Traverse the string, S
for (let i = 0; i < N; i++) {
// If stack is empty
if (st.length == 0) {
// There is no 1 that can
// change this 0 to 1
if (S[i] == '0') {
flag = 0;
break;
}
// Push 1 into the stack
count = 0;
st.push(S[i]);
}
else {
if (S[i] == '0') {
count++;
// The last 1 has reached
// its limit
if (count == K) {
st.pop();
count = 0;
}
}
// New 1 has been found which
// can now change at most K 0s
else {
count = 0;
}
}
}
// If flag is 1, print "YES"
// else print "NO"
if (flag == 1)
document.write("YES");
else
document.write("NO");
}
// Driver code
// Given Input
let S = "100100";
let N = S.Length;
let K = 2;
// Function call
changeCharacters(S, N, K);
// This code is contributed by _saurabh_jaiswal
</script>
Producción
YES
Complejidad de tiempo: O(N)
Espacio auxiliar: O(1) ya que como máximo un carácter está presente en la pila en cualquier momento
Publicación traducida automáticamente
Artículo escrito por kaustubhkale10324 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA