Dada una string S de longitud N que consta de 1 , 0 y X , la tarea es imprimir el carácter ( ‘1’ o ‘0’ ) con la frecuencia máxima después de reemplazar cada aparición de X según las siguientes condiciones:
- Si el carácter presente adyacente a la izquierda de X es 1 , reemplace X con 1 .
- Si el carácter presente junto a la derecha de X es 0 , reemplace X con 0 .
- Si se cumplen las dos condiciones anteriores, X permanece sin cambios.
Nota: si la frecuencia de 1 y 0 es la misma después de los reemplazos, imprima X .
Ejemplos:
Entrada: S = “XX10XX10XXX1XX”
Salida: 1
Explicación:
Operación 1: S = “X11001100X1XX”
Operación 2: S = “111001100X1XX”
No son posibles más sustituciones.
Por lo tanto, las frecuencias de ‘1’ y ‘0’ son 6 y 4 respectivamente.Entrada: S = “0XXX1”
Salida: X
Explicación:
Operación 1: S = “00X11”
No son posibles más sustituciones.
Por lo tanto, las frecuencias de ‘1’ y ‘0’ son 2.
Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:
- Todas las ‘X’ que se encuentran entre ‘1’ y ‘0’ ( por ejemplo , 1XXX0 ) no tienen importancia porque ni ‘1’ ni ‘0’ pueden convertirlo.
- Todas las ‘X’ que se encuentran entre ‘0’ y ‘1’ ( por ejemplo , 0XXX1 ) tampoco tienen importancia porque contribuirán por igual a 1 y 0 . Considere cualquier substring de la forma “0X….X1” , luego de cambiar la primera aparición de X desde el principio y el final de la string, la frecuencia real de 0 y 1 en la substring permanece sin cambios.
De las observaciones anteriores se puede concluir que el resultado depende de las siguientes condiciones:
- La cuenta de ‘1’ y ‘0’ en la string original.
- La frecuencia de X que están presentes entre dos 0 s consecutivos o dos 1 s consecutivos, es decir, “0XXX0” y “1XXXX1” respectivamente.
- El número de ‘X’ continuas que están presentes al comienzo de la string y tienen un extremo derecho ‘1’ , es decir, “XXXX1…..” .
- El número de ‘X’ continuas que están presentes al final de la string y tiene un extremo izquierdo ‘0’ , es decir, …..0XXX .
Por lo tanto, cuente el número de 1 s y 0 s según las condiciones anteriores e imprima la cuenta resultante.
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 find the most frequent
// character after replacing X with
// either '0' or '1' according as per
// the given conditions
void maxOccurringCharacter(string s)
{
// Store the count of 0s and
// 1s in the string S
int count0 = 0, count1 = 0;
// Count the frequency of
// 0 and 1
for (int i = 0; i < s.length(); i++) {
// If the character is 1
if (s[i] == '1') {
count1++;
}
// If the character is 0
else if (s[i] == '0') {
count0++;
}
}
// Stores first occurrence of 1
int prev = -1;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '1') {
prev = i;
break;
}
}
// Traverse the string to count
// the number of X between two
// consecutive 1s
for (int i = prev + 1; i < s.length(); i++) {
// If the current character
// is not X
if (s[i] != 'X') {
// If the current character
// is 1, add the number of
// Xs to count1 and set
// prev to i
if (s[i] == '1') {
count1 += i - prev - 1;
prev = i;
}
// Otherwise
else {
// Find next occurrence
// of 1 in the string
bool flag = true;
for (int j = i + 1; j < s.length(); j++) {
if (s[j] == '1') {
flag = false;
prev = j;
break;
}
}
// If it is found,
// set i to prev
if (!flag) {
i = prev;
}
// Otherwise, break
// out of the loop
else {
i = s.length();
}
}
}
}
// Store the first occurrence of 0
prev = -1;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '0') {
prev = i;
break;
}
}
// Repeat the same procedure to
// count the number of X between
// two consecutive 0s
for (int i = prev + 1; i < s.length(); i++) {
// If the current character is not X
if (s[i] != 'X') {
// If the current character is 0
if (s[i] == '0') {
// Add the count of Xs to count0
count0 += i - prev - 1;
// Set prev to i
prev = i;
}
// Otherwise
else {
// Find the next occurrence
// of 0 in the string
bool flag = true;
for (int j = i + 1; j < s.length(); j++) {
if (s[j] == '0') {
prev = j;
flag = false;
break;
}
}
// If it is found,
// set i to prev
if (!flag) {
i = prev;
}
// Otherwise, break out
// of the loop
else {
i = s.length();
}
}
}
}
// Count number of X present in
// the starting of the string
// as XXXX1...
if (s[0] == 'X') {
// Store the count of X
int count = 0;
int i = 0;
while (s[i] == 'X') {
count++;
i++;
}
// Increment count1 by
// count if the condition
// is satisfied
if (s[i] == '1') {
count1 += count;
}
}
// Count the number of X
// present in the ending of
// the string as ...XXXX0
if (s[(s.length() - 1)] == 'X') {
// Store the count of X
int count = 0;
int i = s.length() - 1;
while (s[i] == 'X') {
count++;
i--;
}
// Increment count0 by
// count if the condition
// is satisfied
if (s[i] == '0') {
count0 += count;
}
}
// If count of 1 is equal to
// count of 0, print X
if (count0 == count1) {
cout << "X" << endl;
}
// Otherwise, if count of 1
// is greater than count of 0
else if (count0 > count1) {
cout << 0 << endl;
}
// Otherwise, print 0
else
cout << 1 << endl;
}
// Driver Code
int main()
{
string S = "XX10XX10XXX1XX";
maxOccurringCharacter(S);
}
// This code is contributed by SURENDAR_GANGWAR.
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to find the most frequent
// character after replacing X with
// either '0' or '1' according as per
// the given conditions
public static void
maxOccurringCharacter(String s)
{
// Store the count of 0s and
// 1s in the string S
int count0 = 0, count1 = 0;
// Count the frequency of
// 0 and 1
for (int i = 0;
i < s.length(); i++) {
// If the character is 1
if (s.charAt(i) == '1') {
count1++;
}
// If the character is 0
else if (s.charAt(i) == '0') {
count0++;
}
}
// Stores first occurrence of 1
int prev = -1;
for (int i = 0;
i < s.length(); i++) {
if (s.charAt(i) == '1') {
prev = i;
break;
}
}
// Traverse the string to count
// the number of X between two
// consecutive 1s
for (int i = prev + 1;
i < s.length(); i++) {
// If the current character
// is not X
if (s.charAt(i) != 'X') {
// If the current character
// is 1, add the number of
// Xs to count1 and set
// prev to i
if (s.charAt(i) == '1') {
count1 += i - prev - 1;
prev = i;
}
// Otherwise
else {
// Find next occurrence
// of 1 in the string
boolean flag = true;
for (int j = i + 1;
j < s.length();
j++) {
if (s.charAt(j) == '1') {
flag = false;
prev = j;
break;
}
}
// If it is found,
// set i to prev
if (!flag) {
i = prev;
}
// Otherwise, break
// out of the loop
else {
i = s.length();
}
}
}
}
// Store the first occurrence of 0
prev = -1;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == '0') {
prev = i;
break;
}
}
// Repeat the same procedure to
// count the number of X between
// two consecutive 0s
for (int i = prev + 1;
i < s.length(); i++) {
// If the current character is not X
if (s.charAt(i) != 'X') {
// If the current character is 0
if (s.charAt(i) == '0') {
// Add the count of Xs to count0
count0 += i - prev - 1;
// Set prev to i
prev = i;
}
// Otherwise
else {
// Find the next occurrence
// of 0 in the string
boolean flag = true;
for (int j = i + 1;
j < s.length(); j++) {
if (s.charAt(j) == '0') {
prev = j;
flag = false;
break;
}
}
// If it is found,
// set i to prev
if (!flag) {
i = prev;
}
// Otherwise, break out
// of the loop
else {
i = s.length();
}
}
}
}
// Count number of X present in
// the starting of the string
// as XXXX1...
if (s.charAt(0) == 'X') {
// Store the count of X
int count = 0;
int i = 0;
while (s.charAt(i) == 'X') {
count++;
i++;
}
// Increment count1 by
// count if the condition
// is satisfied
if (s.charAt(i) == '1') {
count1 += count;
}
}
// Count the number of X
// present in the ending of
// the string as ...XXXX0
if (s.charAt(s.length() - 1)
== 'X') {
// Store the count of X
int count = 0;
int i = s.length() - 1;
while (s.charAt(i) == 'X') {
count++;
i--;
}
// Increment count0 by
// count if the condition
// is satisfied
if (s.charAt(i) == '0') {
count0 += count;
}
}
// If count of 1 is equal to
// count of 0, print X
if (count0 == count1) {
System.out.println("X");
}
// Otherwise, if count of 1
// is greater than count of 0
else if (count0 > count1) {
System.out.println(0);
}
// Otherwise, print 0
else
System.out.println(1);
}
// Driver Code
public static void main(String[] args)
{
String S = "XX10XX10XXX1XX";
maxOccurringCharacter(S);
}
}
Python3
# Python program for the above approach
# Function to find the most frequent
# character after replacing X with
# either '0' or '1' according as per
# the given conditions
def maxOccurringCharacter(s):
# Store the count of 0s and
# 1s in the S
count0 = 0
count1 = 0
# Count the frequency of
# 0 and 1
for i in range(len(s)):
# If the character is 1
if (s[i] == '1') :
count1 += 1
# If the character is 0
elif (s[i] == '0') :
count0 += 1
# Stores first occurrence of 1
prev = -1
for i in range(len(s)):
if (s[i] == '1') :
prev = i
break
# Traverse the to count
# the number of X between two
# consecutive 1s
for i in range(prev + 1, len(s)):
# If the current character
# is not X
if (s[i] != 'X') :
# If the current character
# is 1, add the number of
# Xs to count1 and set
# prev to i
if (s[i] == '1') :
count1 += i - prev - 1
prev = i
# Otherwise
else :
# Find next occurrence
# of 1 in the string
flag = True
for j in range(i+1, len(s)):
if (s[j] == '1') :
flag = False
prev = j
break
# If it is found,
# set i to prev
if (flag == False) :
i = prev
# Otherwise, break
# out of the loop
else :
i = len(s)
# Store the first occurrence of 0
prev = -1
for i in range(0, len(s)):
if (s[i] == '0') :
prev = i
break
# Repeat the same procedure to
# count the number of X between
# two consecutive 0s
for i in range(prev + 1, len(s)):
# If the current character is not X
if (s[i] != 'X') :
# If the current character is 0
if (s[i] == '0') :
# Add the count of Xs to count0
count0 += i - prev - 1
# Set prev to i
prev = i
# Otherwise
else :
# Find the next occurrence
# of 0 in the string
flag = True
for j in range(i + 1, len(s)):
if (s[j] == '0') :
prev = j
flag = False
break
# If it is found,
# set i to prev
if (flag == False) :
i = prev
# Otherwise, break out
# of the loop
else :
i = len(s)
# Count number of X present in
# the starting of the string
# as XXXX1...
if (s[0] == 'X') :
# Store the count of X
count = 0
i = 0
while (s[i] == 'X') :
count += 1
i += 1
# Increment count1 by
# count if the condition
# is satisfied
if (s[i] == '1') :
count1 += count
# Count the number of X
# present in the ending of
# the as ...XXXX0
if (s[(len(s) - 1)]
== 'X') :
# Store the count of X
count = 0
i = len(s) - 1
while (s[i] == 'X') :
count += 1
i -= 1
# Increment count0 by
# count if the condition
# is satisfied
if (s[i] == '0') :
count0 += count
# If count of 1 is equal to
# count of 0, print X
if (count0 == count1) :
print("X")
# Otherwise, if count of 1
# is greater than count of 0
elif (count0 > count1) :
print( 0 )
# Otherwise, print 0
else:
print(1)
# Driver Code
S = "XX10XX10XXX1XX"
maxOccurringCharacter(S)
# This code is contributed by sanjoy_62.
C#
// C# program for the above approach
using System;
public class GFG
{
// Function to find the most frequent
// character after replacing X with
// either '0' or '1' according as per
// the given conditions
public static void maxOccurringCharacter(string s)
{
// Store the count of 0s and
// 1s in the string S
int count0 = 0, count1 = 0;
// Count the frequency of
// 0 and 1
for (int i = 0;
i < s.Length; i++) {
// If the character is 1
if (s[i] == '1') {
count1++;
}
// If the character is 0
else if (s[i] == '0') {
count0++;
}
}
// Stores first occurrence of 1
int prev = -1;
for (int i = 0;
i < s.Length; i++) {
if (s[i] == '1') {
prev = i;
break;
}
}
// Traverse the string to count
// the number of X between two
// consecutive 1s
for (int i = prev + 1;
i < s.Length; i++) {
// If the current character
// is not X
if (s[i] != 'X') {
// If the current character
// is 1, add the number of
// Xs to count1 and set
// prev to i
if (s[i] == '1') {
count1 += i - prev - 1;
prev = i;
}
// Otherwise
else {
// Find next occurrence
// of 1 in the string
bool flag = true;
for (int j = i + 1;
j < s.Length;
j++) {
if (s[j] == '1') {
flag = false;
prev = j;
break;
}
}
// If it is found,
// set i to prev
if (!flag) {
i = prev;
}
// Otherwise, break
// out of the loop
else {
i = s.Length;
}
}
}
}
// Store the first occurrence of 0
prev = -1;
for (int i = 0; i < s.Length; i++) {
if (s[i] == '0') {
prev = i;
break;
}
}
// Repeat the same procedure to
// count the number of X between
// two consecutive 0s
for (int i = prev + 1;
i < s.Length; i++) {
// If the current character is not X
if (s[i] != 'X') {
// If the current character is 0
if (s[i] == '0') {
// Add the count of Xs to count0
count0 += i - prev - 1;
// Set prev to i
prev = i;
}
// Otherwise
else {
// Find the next occurrence
// of 0 in the string
bool flag = true;
for (int j = i + 1;
j < s.Length; j++) {
if (s[j] == '0') {
prev = j;
flag = false;
break;
}
}
// If it is found,
// set i to prev
if (!flag) {
i = prev;
}
// Otherwise, break out
// of the loop
else {
i = s.Length;
}
}
}
}
// Count number of X present in
// the starting of the string
// as XXXX1...
if (s[0] == 'X') {
// Store the count of X
int count = 0;
int i = 0;
while (s[i] == 'X') {
count++;
i++;
}
// Increment count1 by
// count if the condition
// is satisfied
if (s[i] == '1') {
count1 += count;
}
}
// Count the number of X
// present in the ending of
// the string as ...XXXX0
if (s[s.Length - 1]
== 'X') {
// Store the count of X
int count = 0;
int i = s.Length - 1;
while (s[i] == 'X') {
count++;
i--;
}
// Increment count0 by
// count if the condition
// is satisfied
if (s[i] == '0') {
count0 += count;
}
}
// If count of 1 is equal to
// count of 0, print X
if (count0 == count1) {
Console.WriteLine("X");
}
// Otherwise, if count of 1
// is greater than count of 0
else if (count0 > count1) {
Console.WriteLine(0);
}
// Otherwise, print 0
else
Console.WriteLine(1);
}
// Driver Code
public static void Main(string[] args)
{
string S = "XX10XX10XXX1XX";
maxOccurringCharacter(S);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// javascript program for the above approach
// Function to find the most frequent
// character after replacing X with
// either '0' or '1' according as per
// the given conditions
function maxOccurringCharacter(s)
{
// Store the count of 0s and
// 1s in the string S
var count0 = 0, count1 = 0;
// Count the frequency of
// 0 and 1
for (var i = 0;
i < s.length; i++) {
// If the character is 1
if (s.charAt(i) == '1') {
count1++;
}
// If the character is 0
else if (s.charAt(i) == '0') {
count0++;
}
}
// Stores first occurence of 1
var prev = -1;
for (var i = 0;
i < s.length; i++) {
if (s.charAt(i) == '1') {
prev = i;
break;
}
}
// Traverse the string to count
// the number of X between two
// consecutive 1s
for (var i = prev + 1;
i < s.length; i++) {
// If the current character
// is not X
if (s.charAt(i) != 'X') {
// If the current character
// is 1, add the number of
// Xs to count1 and set
// prev to i
if (s.charAt(i) == '1') {
count1 += i - prev - 1;
prev = i;
}
// Otherwise
else {
// Find next occurrence
// of 1 in the string
flag = true;
for (var j = i + 1;
j < s.length;
j++) {
if (s.charAt(j) == '1') {
flag = false;
prev = j;
break;
}
}
// If it is found,
// set i to prev
if (!flag) {
i = prev;
}
// Otherwise, break
// out of the loop
else {
i = s.length;
}
}
}
}
// Store the first occurrence of 0
prev = -1;
for (var i = 0; i < s.length; i++) {
if (s.charAt(i) == '0') {
prev = i;
break;
}
}
// Repeat the same procedure to
// count the number of X between
// two consecutive 0s
for (var i = prev + 1;
i < s.length; i++) {
// If the current character is not X
if (s.charAt(i) != 'X') {
// If the current character is 0
if (s.charAt(i) == '0') {
// Add the count of Xs to count0
count0 += i - prev - 1;
// Set prev to i
prev = i;
}
// Otherwise
else {
// Find the next occurrence
// of 0 in the string
flag = true;
for (var j = i + 1;
j < s.length; j++) {
if (s.charAt(j) == '0') {
prev = j;
flag = false;
break;
}
}
// If it is found,
// set i to prev
if (!flag) {
i = prev;
}
// Otherwise, break out
// of the loop
else {
i = s.length;
}
}
}
}
// Count number of X present in
// the starting of the string
// as XXXX1...
if (s.charAt(0) == 'X') {
// Store the count of X
var count = 0;
var i = 0;
while (s.charAt(i) == 'X') {
count++;
i++;
}
// Increment count1 by
// count if the condition
// is satisfied
if (s.charAt(i) == '1') {
count1 += count;
}
}
// Count the number of X
// present in the ending of
// the string as ...XXXX0
if (s.charAt(s.length - 1)
== 'X') {
// Store the count of X
var count = 0;
var i = s.length - 1;
while (s.charAt(i) == 'X') {
count++;
i--;
}
// Increment count0 by
// count if the condition
// is satisfied
if (s.charAt(i) == '0') {
count0 += count;
}
}
// If count of 1 is equal to
// count of 0, print X
if (count0 == count1) {
document.write("X");
}
// Otherwise, if count of 1
// is greater than count of 0
else if (count0 > count1) {
document.write(0);
}
// Otherwise, print 0
else
document.write(1);
}
// Driver Code
var S = "XX10XX10XXX1XX";
maxOccurringCharacter(S);
// This code is contributed by 29AjayKumar
</script>
Producción:
1
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aditya7409 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA