Dada una string S de tamaño N que consta de ‘0’, ‘1’ y ‘?’, donde N siempre es par. Divida la string en dos strings diferentes, digamos S1 y S2 , donde S1 solo contendrá los caracteres en los índices pares de S y S2 solo contendrá los caracteres en los índices impares de S. La tarea es encontrar los pasos mínimos posibles requeridos para predecir cuál de las dos strings S1 y S2 tendrá la cuenta máxima de 1. En un solo paso, elija un carácter para cualquieraS1 o S2. Si el carácter es ‘ 0 ‘, elija ‘ 0 ‘, si el carácter es ‘ 1 ‘, elija ‘ 1 ‘ y si el carácter es ‘ ? ‘ luego elija cualquiera de ‘ 1 ‘ o ‘ 0 ‘.
Ejemplo:
Entrada: s = “?10?0?”
Salida: 4
Explicación:
Paso 1: Para que el carácter S1 elija es S[0]=’?’, así que elija ‘0’. S1=”0″, S2=””.
Paso 2: Para que el carácter S2 elija es S[1]=’1′, así que elija ‘1’. S1=”0″, S2=”1″.
Paso 1: Para que el carácter S1 elija es S[2]=’?’, así que elija ‘0’. S1=”00″, S2=”1″.
Paso 1: Para que el carácter S1 elija es S[3]=’?’, así que elija ‘1’. S1=”00″, S2=”11″.
Después del paso 4, S2 tendrá más números de 1, independientemente del número que se elija para los índices restantes.Entrada: s = “?1?0??0110”
Salida: 7
Enfoque: La idea es resolver el problema recursivamente y responder esto después de explorar todos los resultados posibles. Ahora, para resolver este problema, siga los siguientes pasos:
- Cree una función llamada minSteps que tenga parámetros, string S , un puntero i que apuntará a la ubicación actual en la string hasta la cual se divide la string, números enteros cuenta1 y cuenta2 que almacenará el número de unos hasta i en S1 y S2 respectivamente, números enteros primero y segundo para almacenar los lugares disponibles en S1 y S2 para los que no se elige ningún valor, y un número entero n que denota el tamaño de la string S. Esta función devolverá los pasos mínimos necesarios para predecir la respuesta.
- Ahora, inicialmente, el puntero actual está en cero, por lo que i=0 . Dado que no se eligieron valores para S1 y S2 hasta ahora y todos los lugares en S1 y S2 están disponibles para llenar, entonces cuenta1=0 , cuenta2=0 , primero = n/2 y segundo=n/2 . Entonces, ahora haz una llamada a la función minPasos con estos argumentos.
- En cada llamada de la función minPasos :
- Verifique los casos base, que son:
- Si i llega a n (es decir, i=n ) porque esto significa que tanto S1 como S2 están completamente llenos, y ahora definitivamente se puede predecir la respuesta. Entonces, devuelve 0.
- Si count1 se vuelve mayor que la suma de second y count2 , devuelve 0, porque ahora, incluso después de seleccionar todos los lugares disponibles en S2 , S1 tendrá más unidades.
- Si count2 se vuelve mayor que la suma de primero y count1 , entonces devuelve 0, por la razón mencionada anteriormente.
- Después de verificar los casos base, verifique si i es par o impar. Si i es par, S1 elige este índice; de lo contrario , S2 .
- Por lo tanto, disminuya el primero o el segundo en función de la string que se está llenando actualmente, porque los lugares disponibles en esa string se reducirán en un lugar después del llenado.
- Ahora bien, si el carácter actual es ‘?’ (es decir , s[i] = ‘?’ ) luego haga ambas llamadas recursivas de elegir ‘1’ y de elegir ‘0’, y devuelva el mínimo de los dos después de agregarles 1.
- De lo contrario, haga una sola llamada y devuelva la respuesta después de agregar una a eso.
- Verifique los casos base, que son:
- La última llamada recursiva dará la respuesta a esta pregunta.
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;
//// Recursive function to minimum steps
// required after combining two strings
int minSteps(string& S, int i, int count1, int count2,
int first, int second, int n)
{
// If current pointer reaches the end
if (i == n) {
return 0;
}
// Condition to conclude that one string does
// more ones than the other irrespective of what
// number is chosen for the remaining indexes
if (count1 > (second + count2)
|| count2 > (first + count1)) {
return 0;
}
int c1 = 0, c2 = 0;
// If i is even, then choosing character for S1
if (i % 2 == 0) {
if (S[i] == '?') {
return min(
1
+ minSteps(
S, i + 1,
count1 + 1, count2,
first - 1, second, n),
1
+ minSteps(
S, i + 1, count1, count2,
first - 1, second, n));
}
else if (S[i] == '1') {
c1 = 1
+ minSteps(
S, i + 1,
count1 + 1, count2,
first - 1, second, n);
return c1;
}
else {
c2 = 1
+ minSteps(
S, i + 1,
count1, count2,
first - 1, second, n);
return c2;
}
}
// If i is odd
else {
if (S[i] == '?') {
return min(
1
+ minSteps(
S, i + 1,
count1, count2 + 1,
first, second - 1, n),
1
+ minSteps(
S, i + 1,
count1, count2,
first, second - 1, n));
}
else if (S[i] == '1') {
c1 = 1
+ minSteps(
S, i + 1,
count1, count2 + 1,
first, second - 1, n);
return c1;
}
else {
c2 = 1
+ minSteps(
S, i + 1, count1,
count2, first,
second - 1, n);
return c2;
}
}
}
// Driver Code
int main()
{
string s = "?10?0?";
int N = s.size();
cout << minSteps(s, 0, 0, 0,
N / 2, N / 2, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG
{
//// Recursive function to minimum steps
// required after combining two strings
static int minSteps(String S, int i, int count1, int count2,
int first, int second, int n)
{
// If current pointer reaches the end
if (i == n) {
return 0;
}
// Condition to conclude that one string does
// more ones than the other irrespective of what
// number is chosen for the remaining indexes
if (count1 > (second + count2)
|| count2 > (first + count1)) {
return 0;
}
int c1 = 0, c2 = 0;
// If i is even, then choosing character for S1
if (i % 2 == 0) {
if (S.charAt(i) == '?') {
return Math.min(
1
+ minSteps(
S, i + 1,
count1 + 1, count2,
first - 1, second, n),
1
+ minSteps(
S, i + 1, count1, count2,
first - 1, second, n));
}
else if (S.charAt(i) == '1') {
c1 = 1
+ minSteps(
S, i + 1,
count1 + 1, count2,
first - 1, second, n);
return c1;
}
else {
c2 = 1
+ minSteps(
S, i + 1,
count1, count2,
first - 1, second, n);
return c2;
}
}
// If i is odd
else {
if (S.charAt(i) == '?') {
return Math. min(
1
+ minSteps(
S, i + 1,
count1, count2 + 1,
first, second - 1, n),
1
+ minSteps(
S, i + 1,
count1, count2,
first, second - 1, n));
}
else if (S.charAt(i) == '1') {
c1 = 1
+ minSteps(
S, i + 1,
count1, count2 + 1,
first, second - 1, n);
return c1;
}
else {
c2 = 1
+ minSteps(
S, i + 1, count1,
count2, first,
second - 1, n);
return c2;
}
}
}
// Driver code
public static void main (String[] args)
{
String s = "?10?0?";
int N = s.length();
System.out.println(minSteps(s, 0, 0, 0,
N / 2, N / 2, N));
}
}
// This code is contributed by sanjoy_62.
Python3
# Python code for the above approach import math # Recursive function to minimum steps # required after combining two strings def minSteps(S, i, count1, count2, first, second, n): # If current pointer reaches the end if i == n: return 0 # Condition to conclude that one string does # more ones than the other irrespective of what # number is chosen for the remaining indexes if count1 > second + count2 or count2 > first + count1: return 0 c1 = 0 c2 = 0 # If i is even, then choosing character for S1 if i % 2 == 0: if S[i] == '?': return min( 1 + minSteps( S, i + 1, count1 + 1, count2, first - 1, second, n), 1 + minSteps( S, i + 1, count1, count2, first - 1, second, n)) elif S[i] == '1': c1 = 1 + minSteps( S, i + 1, count1 + 1, count2, first - 1, second, n) return c1 else: c2 = 1 + minSteps( S, i + 1, count1, count2, first - 1, second, n) return c2 # If i is odd else: if S[i] == '?': return min( 1 + minSteps( S, i + 1, count1, count2 + 1, first, second - 1, n), 1 + minSteps( S, i + 1, count1, count2, first, second - 1, n)) elif S[i] == '1': c1 = 1 + minSteps( S, i + 1, count1, count2 + 1, first, second - 1, n) return c1 else: c2 = 1 + minSteps( S, i + 1, count1, count2, first, second - 1, n) return c2 # Driver Code s = "?10?0?" N = len(s) print(minSteps(s, 0, 0, 0, math.floor(N / 2), math.floor(N / 2), N)) # This code is contributed by Potta Lokesh
C#
// C# program for the above approach
using System;
class GFG
{
//// Recursive function to minimum steps
// required after combining two strings
static int minSteps(string S, int i, int count1, int count2,
int first, int second, int n)
{
// If current pointer reaches the end
if (i == n) {
return 0;
}
// Condition to conclude that one string does
// more ones than the other irrespective of what
// number is chosen for the remaining indexes
if (count1 > (second + count2)
|| count2 > (first + count1)) {
return 0;
}
int c1 = 0, c2 = 0;
// If i is even, then choosing character for S1
if (i % 2 == 0) {
if (S[i] == '?') {
return Math.Min(
1
+ minSteps(
S, i + 1,
count1 + 1, count2,
first - 1, second, n),
1
+ minSteps(
S, i + 1, count1, count2,
first - 1, second, n));
}
else if (S[i] == '1') {
c1 = 1
+ minSteps(
S, i + 1,
count1 + 1, count2,
first - 1, second, n);
return c1;
}
else {
c2 = 1
+ minSteps(
S, i + 1,
count1, count2,
first - 1, second, n);
return c2;
}
}
// If i is odd
else {
if (S[i] == '?') {
return Math.Min(
1
+ minSteps(
S, i + 1,
count1, count2 + 1,
first, second - 1, n),
1
+ minSteps(
S, i + 1,
count1, count2,
first, second - 1, n));
}
else if (S[i] == '1') {
c1 = 1
+ minSteps(
S, i + 1,
count1, count2 + 1,
first, second - 1, n);
return c1;
}
else {
c2 = 1
+ minSteps(
S, i + 1, count1,
count2, first,
second - 1, n);
return c2;
}
}
}
// Driver code
public static void Main ()
{
string s = "?10?0?";
int N = s.Length;
Console.Write(minSteps(s, 0, 0, 0,
N / 2, N / 2, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Javascript
<script>
// Javascript program for the above approach
//// Recursive function to minimum steps
// required after combining two strings
function minSteps(S, i, count1, count2,
first, second, n)
{
// If current pointer reaches the end
if (i == n) {
return 0;
}
// Condition to conclude that one string does
// more ones than the other irrespective of what
// number is chosen for the remaining indexes
if (count1 > (second + count2)
|| count2 > (first + count1)) {
return 0;
}
let c1 = 0, c2 = 0;
// If i is even, then choosing character for S1
if (i % 2 == 0) {
if (S[i] == '?') {
return Math.min(
1
+ minSteps(
S, i + 1,
count1 + 1, count2,
first - 1, second, n),
1
+ minSteps(
S, i + 1, count1, count2,
first - 1, second, n));
}
else if (S[i] == '1') {
c1 = 1
+ minSteps(
S, i + 1,
count1 + 1, count2,
first - 1, second, n);
return c1;
}
else {
c2 = 1
+ minSteps(
S, i + 1,
count1, count2,
first - 1, second, n);
return c2;
}
}
// If i is odd
else {
if (S[i] == '?') {
return Math.min(
1
+ minSteps(
S, i + 1,
count1, count2 + 1,
first, second - 1, n),
1
+ minSteps(
S, i + 1,
count1, count2,
first, second - 1, n));
}
else if (S[i] == '1') {
c1 = 1
+ minSteps(
S, i + 1,
count1, count2 + 1,
first, second - 1, n);
return c1;
}
else {
c2 = 1
+ minSteps(
S, i + 1, count1,
count2, first,
second - 1, n);
return c2;
}
}
}
// Driver Code
let s = "?10?0?";
let N = s.length;
document.write(minSteps(s, 0, 0, 0,
N / 2, N / 2, N));
// This code is contributed by Samim Hossain Mondal.
</script>
Producción
4
Complejidad de tiempo: O(2^N)
Espacio auxiliar: O(1)