Dada una string binaria S de tamaño N , la tarea es verificar si el conteo de 1 puede hacerse mayor que el conteo de 0 cambiando los 0 adyacentes a 1 por cualquier otro carácter. Si es posible, imprima Sí . De lo contrario , imprima No.
Nota: Cualquier índice que tenga 1 se puede elegir como máximo una vez.
Ejemplos:
Entrada: S = “01”
Salida: Sí
Explicación:
Elija ‘1’ en el índice 1 y cambie su 0 adyacente izquierdo a ‘_’, modifica la string a “_1”.
Ahora, la cuenta de 1 es 1, que es mayor que la cuenta de 0, es decir, 0. Por lo tanto, imprima Sí.Entrada: S = “001110000”
Salida: No
Enfoque: el problema dado se puede resolver contando el número de 1 y 0 en la string S y luego, al atravesar la string, si hay algún índice i en el que el valor sea ‘1’ y si es del lado izquierdo o derecho (no ambos). ) es ‘0’ y luego cámbielo a ‘_’ . El valor se cambia a ‘_’ y no a ‘1’ para que no se vuelva a utilizar. Después de cambiar el valor, disminuya la cuenta de 0 en 1 . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos cnt0 y cnt1 como 0 para almacenar el recuento de 0 y 1 .
- Recorra la string S y almacene el conteo de 1 y 0 en las variables cnt0 y cnt1 respectivamente.
- Recorra la string S desde el lado izquierdo y verifique que el carácter actual sea 1 si se encuentra que es verdadero, luego verifique la condición:
- if(i > 0 && S[i – 1] == ‘0’) si se encuentra que es verdadero, entonces cambie el 0 adyacente izquierdo a S[i-1] = ‘_’ y disminuya el valor de cnt0 en 1 .
- else if(i < S.length() && S[i+1] == ‘0’) si se encuentra que es verdadero, entonces cambie el 0 derecho a S[i+1] = ‘_’ y disminuya el valor de cnt0 por 1 .
- Después de completar los pasos anteriores, si el valor de (cnt1 > cnt0) , imprima «Sí» . De lo contrario, escriba “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 whether in a given
// binary string can we make number of
// 1's greater than the number of 0's
// by doing the given operation
void isOnesGreater(string S, int N)
{
// Stores the count of 0's
int cnt0 = 0;
// Stores the count of 1's
int cnt1 = 0;
// Traverse through the string S
for (int i = 0; i < N; i++) {
// Check current character is 1
if (S[i] == '1')
// Update cnt1
cnt1++;
else
// Update cnt0
cnt0++;
}
// Traverse through the string S
for (int i = 0; i < N; i++) {
// Check curretn character is 1
if (S[i] == '1') {
// Check if left adjacent
// character is 0
if (i > 0 && S[i - 1] == '0') {
// Change the left adjacent
// character to _
S[i - 1] = '_';
// Update the cnt0
cnt0--;
}
// Check if right adjacent
// character is 0
else if (i < N && S[i + 1] == '0') {
// Change the right adjacent
// character to _
S[i + 1] = '_';
// Update the cnt0
cnt0--;
}
}
}
// Check count of 1's is greater
// than the count of 0's
if (cnt1 > cnt0) {
cout << "Yes";
}
else {
cout << "No";
}
}
// Driver Code
int main()
{
string S = "01";
int N = S.length();
isOnesGreater(S, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to check whether in a given
// binary string can we make number of
// 1's greater than the number of 0's
// by doing the given operation
static void isOnesGreater(String S, int N)
{
char[] st = new char[S.length()];
// Copy character by character into array
for (int i = 0; i < S.length(); i++) {
st[i] = S.charAt(i);
}
// Stores the count of 0's
int cnt0 = 0;
// Stores the count of 1's
int cnt1 = 0;
// Traverse through the string S
for (int i = 0; i < N; i++) {
// Check current character is 1
if (st[i] == '1')
// Update cnt1
cnt1++;
else
// Update cnt0
cnt0++;
}
// Traverse through the string S
for (int i = 0; i < N; i++) {
// Check curretn character is 1
if (st[i] == '1') {
// Check if left adjacent
// character is 0
if (i > 0 && st[i - 1] == '0') {
// Change the left adjacent
// character to _
st[i - 1] = '_';
// Update the cnt0
cnt0--;
}
// Check if right adjacent
// character is 0
else if (i < N && st[i + 1] == '0') {
// Change the right adjacent
// character to _
st[i + 1] = '_';
// Update the cnt0
cnt0--;
}
}
}
// Check count of 1's is greater
// than the count of 0's
if (cnt1 > cnt0) {
System.out.println("Yes");
}
else {
System.out.println("No");
}
}
// Driver Code
public static void main(String args[])
{
String S = "01";
int N = S.length();
isOnesGreater(S, N);
}
}
// This code is contributed by bgangwar59.
Python3
# Python Program to implement
# the above approach
# Function to check whether in a given
# binary string can we make number of
# 1's greater than the number of 0's
# by doing the given operation
def isOnesGreater(S, N):
S = list(S)
# Stores the count of 0's
cnt0 = 0
# Stores the count of 1's
cnt1 = 0
# Traverse through the string S
for i in range(N):
# Check current character is 1
if (S[i] == '1'):
# Update cnt1
cnt1 += 1
else:
# Update cnt0
cnt0 += 1
# Traverse through the string S
for i in range(N):
# Check curretn character is 1
if (S[i] == '1'):
# Check if left adjacent
# character is 0
if (i > 0 and S[i - 1] == '0'):
# Change the left adjacent
# character to _
S[i - 1] = '_'
# Update the cnt0
cnt0 -= 1
# Check if right adjacent
# character is 0
elif (i < N and S[i + 1] == '0'):
# Change the right adjacent
# character to _
S[i + 1] = '_'
# Update the cnt0
cnt0 -= 1
# Check count of 1's is greater
# than the count of 0's
if (cnt1 > cnt0):
print("Yes")
else:
print("No")
# Driver Code
S = "01"
N = len(S)
isOnesGreater(S, N)
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
using System.Text;
class GFG {
// Function to check whether in a given
// binary string can we make number of
// 1's greater than the number of 0's
// by doing the given operation
static void isOnesGreater(string S, int N)
{
StringBuilder st = new StringBuilder(S);
// Stores the count of 0's
int cnt0 = 0;
// Stores the count of 1's
int cnt1 = 0;
// Traverse through the string S
for (int i = 0; i < N; i++) {
// Check current character is 1
if (st[i] == '1')
// Update cnt1
cnt1++;
else
// Update cnt0
cnt0++;
}
// Traverse through the string S
for (int i = 0; i < N; i++) {
// Check curretn character is 1
if (st[i] == '1') {
// Check if left adjacent
// character is 0
if (i > 0 && st[i - 1] == '0') {
// Change the left adjacent
// character to _
st[i - 1] = '_';
// Update the cnt0
cnt0--;
}
// Check if right adjacent
// character is 0
else if (i < N && st[i + 1] == '0') {
// Change the right adjacent
// character to _
st[i + 1] = '_';
// Update the cnt0
cnt0--;
}
}
}
// Check count of 1's is greater
// than the count of 0's
if (cnt1 > cnt0) {
Console.WriteLine("Yes");
}
else {
Console.WriteLine("No");
}
}
// Driver Code
public static void Main()
{
string S = "01";
int N = S.Length;
isOnesGreater(S, N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to check whether in a given
// binary string can we make number of
// 1's greater than the number of 0's
// by doing the given operation
function isOnesGreater(S, N) {
// Stores the count of 0's
let cnt0 = 0;
// Stores the count of 1's
let cnt1 = 0;
// Traverse through the string S
for (let i = 0; i < N; i++) {
// Check current character is 1
if (S[i] == '1')
// Update cnt1
cnt1++;
else
// Update cnt0
cnt0++;
}
// Traverse through the string S
for (let i = 0; i < N; i++) {
// Check curretn character is 1
if (S[i] == '1') {
// Check if left adjacent
// character is 0
if (i > 0 && S[i - 1] == '0') {
// Change the left adjacent
// character to _
S[i - 1] = '_';
// Update the cnt0
cnt0--;
}
// Check if right adjacent
// character is 0
else if (i < N && S[i + 1] == '0') {
// Change the right adjacent
// character to _
S[i + 1] = '_';
// Update the cnt0
cnt0--;
}
}
}
// Check count of 1's is greater
// than the count of 0's
if (cnt1 > cnt0) {
document.write("Yes");
}
else {
document.write("No");
}
}
// Driver Code
let S = "01";
let N = S.length;
isOnesGreater(S, N);
// This code is contributed by Potta Lokesh
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA