Dada una string binaria S de longitud N y un entero K , la tarea es verificar si es posible invertir K 0 de manera que la string resultante no contenga ningún par de 1 adyacentes . Si es posible hacerlo, escriba «Sí» . De lo contrario, escriba “No” .
Entrada: S = “01001001000”, K = 1
Salida: Sí
Explicación:
Modificar S = “0100100100 0 ” a “01001001001” o modificar S = “010010010 0 0″ a “010010010 1 0″ satisface la condición dada.Entrada: S = “000001000”, K = 4
Salida: No
Enfoque: la idea de atravesar la string y reemplazar esos ‘ 0′ con ‘ 1′ cuyos dos caracteres adyacentes son ‘ 0 ‘ y voltear uno de los ‘ 0 ‘ para contar todas las posiciones posibles de volteos de modo que no t afecta la string original. Siga los pasos a continuación para resolver el problema:
- Inicialice la variable s, digamos cnt como 0, para almacenar el recuento de posiciones que se pueden invertir.
- Recorra la string usando una variable i y realice los siguientes pasos:
- Si el carácter actual es ‘ 1′ , entonces incremente i en 2 .
- De lo contrario:
- Si i = 0 y s[i + 1] = ‘0’: Incremente cnt en 1 e i en 2 . De lo contrario, incremente i en 1 .
- Si i = (N – 1), y s[i – 1] = ‘0’: Incremente cnt en 1 e i en 2 . De lo contrario, incremente i en 1 .
- De lo contrario, si s[i + 1] = ‘0’ y s[i – 1] = ‘0’: Incremente cnt en 1 e i en 2. De lo contrario, incremente i en 1 .
- Después de completar los pasos anteriores, si el valor de cnt es al menos K, imprima «Sí» , de lo contrario, imprima «No» .
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 if k '0's can
// be flipped such that the string
// does not contain any pair of adjacent '1's
void canPlace(string s, int n, int k)
{
// Store the count of flips
int cnt = 0;
// Variable to iterate the string
int i = 0;
// Iterate over characters
// of the string
while (i < n) {
// If the current character
// is '1', increment i by 2
if (s[i] == '1') {
i += 2;
}
// Otherwise, 3 cases arises
else {
// If the current index
// is the starting index
if (i == 0) {
// If next character is '0'
if (s[i + 1] == '0') {
cnt++;
i += 2;
}
// Increment i by 1
else
i++;
}
// If the current index
// is the last index
else if (i == n - 1) {
// If previous character is '0'
if (s[i - 1] == '0') {
cnt++;
i += 2;
}
else
i++;
}
// For remaining characters
else {
// If both the adjacent
// characters are '0'
if (s[i + 1] == '0' && s[i - 1] == '0') {
cnt++;
i += 2;
}
else
i++;
}
}
}
// If cnt is at least K, print "Yes"
if (cnt >= k) {
cout << "Yes";
}
// Otherwise, print "No"
else {
cout << "No";
}
}
// Driver Code
int main()
{
string S = "10001";
int K = 1;
int N = S.size();
canPlace(S, N, K);
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
class GFG
{
// Function to check if k '0's can
// be flipped such that the string
// does not contain any pair of adjacent '1's
public static void canPlace(String s, int n, int k)
{
// Store the count of flips
int cnt = 0;
// Variable to iterate the string
int i = 0;
// Iterate over characters
// of the string
while (i < n)
{
// If the current character
// is '1', increment i by 2
if (s.charAt(i) == '1')
{
i += 2;
}
// Otherwise, 3 cases arises
else
{
// If the current index
// is the starting index
if (i == 0)
{
// If next character is '0'
if (s.charAt(i + 1) == '0')
{
cnt++;
i += 2;
}
// Increment i by 1
else
i++;
}
// If the current index
// is the last index
else if (i == n - 1)
{
// If previous character is '0'
if (s.charAt(i - 1) == '0')
{
cnt++;
i += 2;
}
else
i++;
}
// For remaining characters
else
{
// If both the adjacent
// characters are '0'
if (s.charAt(i + 1) == '0' && s.charAt(i - 1) == '0')
{
cnt++;
i += 2;
}
else
i++;
}
}
}
// If cnt is at least K, print "Yes"
if (cnt >= k)
{
System.out.println("Yes");
}
// Otherwise, print "No"
else
{
System.out.println("No");
}
}
// Driver code
public static void main (String[] args)
{
String S = "10001";
int K = 1;
int N = 5;
canPlace(S, N, K);
}
}
// This code is contributed by manupatharia.
Python3
# Python3 program for the above approach
# Function to check if k '0's can
# be flipped such that the string
# does not contain any pair of adjacent '1's
def canPlace(s, n, k) :
# Store the count of flips
cnt = 0
# Variable to iterate the string
i = 0
# Iterate over characters
# of the string
while (i < n) :
# If the current character
# is '1', increment i by 2
if (s[i] == '1') :
i += 2
# Otherwise, 3 cases arises
else :
# If the current index
# is the starting index
if (i == 0) :
# If next character is '0'
if (s[i + 1] == '0') :
cnt += 1
i += 2
# Increment i by 1
else :
i += 1
# If the current index
# is the last index
elif (i == n - 1) :
# If previous character is '0'
if (s[i - 1] == '0') :
cnt += 1
i += 2
else :
i += 1
# For remaining characters
else :
# If both the adjacent
# characters are '0'
if (s[i + 1] == '0' and s[i - 1] == '0') :
cnt += 1
i += 2
else :
i += 1
# If cnt is at least K, print "Yes"
if (cnt >= k) :
print("Yes")
# Otherwise, print "No"
else :
print("No")
# Driver code
S = "10001"
K = 1
N = len(S)
canPlace(S, N, K)
# This code is contributed by divyeshrabadiya07.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to check if k '0's can
// be flipped such that the string
// does not contain any pair of adjacent '1's
static void canPlace(string s, int n, int k)
{
// Store the count of flips
int cnt = 0;
// Variable to iterate the string
int i = 0;
// Iterate over characters
// of the string
while (i < n) {
// If the current character
// is '1', increment i by 2
if (s[i] == '1') {
i += 2;
}
// Otherwise, 3 cases arises
else {
// If the current index
// is the starting index
if (i == 0) {
// If next character is '0'
if (s[i + 1] == '0') {
cnt++;
i += 2;
}
// Increment i by 1
else
i++;
}
// If the current index
// is the last index
else if (i == n - 1) {
// If previous character is '0'
if (s[i - 1] == '0') {
cnt++;
i += 2;
}
else
i++;
}
// For remaining characters
else {
// If both the adjacent
// characters are '0'
if (s[i + 1] == '0' && s[i - 1] == '0') {
cnt++;
i += 2;
}
else
i++;
}
}
}
// If cnt is at least K, print "Yes"
if (cnt >= k)
{
Console.WriteLine("Yes");
}
// Otherwise, print "No"
else
{
Console.WriteLine("No");
}
}
// Driver Code
public static void Main(String[] args)
{
string S = "10001";
int K = 1;
int N = S.Length;
canPlace(S, N, K);
}
}
// This code is contributed by susmitakundugoaldanga.
Javascript
<script>
/*package whatever //do not write package name here */
// Function to check if k '0's can
// be flipped such that the string
// does not contain any pair of adjacent '1's
function canPlace(s, n, k)
{
// Store the count of flips
var cnt = 0;
// Variable to iterate the string
var i = 0;
// Iterate over characters
// of the string
while (i < n)
{
// If the current character
// is '1', increment i by 2
if (s.charAt(i) == '1')
{
i += 2;
}
// Otherwise, 3 cases arises
else
{
// If the current index
// is the starting index
if (i == 0)
{
// If next character is '0'
if (s.charAt(i + 1) == '0')
{
cnt++;
i += 2;
}
// Increment i by 1
else
i++;
}
// If the current index
// is the last index
else if (i == n - 1)
{
// If previous character is '0'
if (s.charAt(i - 1) == '0')
{
cnt++;
i += 2;
}
else
i++;
}
// For remaining characters
else
{
// If both the adjacent
// characters are '0'
if (s.charAt(i + 1) == '0' && s.charAt(i - 1) == '0')
{
cnt++;
i += 2;
}
else
i++;
}
}
}
// If cnt is at least K, print "Yes"
if (cnt >= k)
{
document.write("Yes");
}
// Otherwise, print "No"
else
{
document.write("No");
}
}
// Driver code
var S = "10001";
var K = 1;
var N = 5;
canPlace(S, N, K);
// This code is contributed by shivanisinghss2110
</script>
Producción:
Yes
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por manupathria y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA