Dadas dos strings binarias S1 y S2 de tamaño N y M respectivamente tales que la string S2 también contiene el carácter ‘?’ , la tarea es encontrar el número de formas de reemplazar ‘?’ en la string S2 tal que la cuenta de 0 y 1 en la string S2 es la misma que en la string S1 .
Ejemplos:
Entrada: S1 = «1010», S2 = «10?»
Salida: 2
Explicación: Las
siguientes son las formas de reemplazar ‘?’ en la string S2:
- Reemplazar «??» en la string S2 con “01” modifica la string S2 = “1001”. Ahora los conteos de 0 y 1 en ambas strings S1 y S2 son iguales.
- Reemplazar «??» en la string S2 con “10” modifica la string S2 = “1010”. Ahora los conteos de 0 y 1 en ambas strings S1 y S2 son iguales.
Por lo tanto, el número total de vías es 2.
Entrada: S1 = “0000”, S2 = “??10?”
Salida: 0
Enfoque: El problema dado se puede resolver usando los conceptos de Combinatoria . Siga los pasos a continuación para resolver el problema:
- Inicialice las variables, digamos, sum1 como 0 , sum2 como 0 que almacena el número de 0 y 1 en la string dada S1 y S2 .
- Inicialice una variable, digamos 0 , que almacene el recuento total de formas de reemplazar ‘?’ en la string S2 que satisface los criterios dados.
- Recorra la string S1 , si el carácter actual es 1 , luego incremente el valor de sum1 en 1. De lo contrario, disminuya el valor de sum1 en 1 .
- Atraviese la string S2 , si el carácter actual es 1 , incremente el valor de sum2 en 1 o si el carácter actual es 0 , disminuya el valor de sum2 en 1 .
- Atraviese la string t , si el carácter actual es ‘+’ incremente el valor de sum2 en 1 . De lo contrario, incremente el valor de K en 1 .
- Inicialice una variable, digamos P que almacene la diferencia absoluta de sum1 y sum2 .
- Si el valor de P es al menos K o el valor de (K – P) es impar, entonces no hay formas posibles de reemplazar ‘?’ y por lo tanto imprima 0 . De lo contrario, imprima el valor de K C (P+K)/2 como el conteo de vías 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 factorial of
// the given number N
int fact(int n)
{
// Stores the factorial
int res = 1;
// Iterate over the range [2, N]
for (int i = 2; i <= n; i++) {
res = res * i;
}
// Return the resultant result
return res;
}
// Function to find the number of ways
// of choosing r objects from n
// distinct objects
int nCr(int n, int r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Function to find the number of ways
// to replace '?' in string t to get
// the same count of 0s and 1s in the
// string S and T
void countWays(string s, string t)
{
int n = s.length();
int sum1 = 0, sum2 = 0, K = 0;
// Traverse the string s
for (int i = 0; i < n; i++) {
// If the current character
// is 1
if (s[i] == '1') {
// Update the value of
// the sum1
sum1++;
}
// Otherwise
else
sum1--;
}
int m = t.length();
// Traverse the string t
for (int i = 0; i < m; i++) {
// If the current character
// is 1, then update the
// value of sum2
if (t[i] == '1') {
sum2++;
}
// If the current character
// is 0
else if (t[i] == '0') {
sum2--;
}
// Otherwise, update the
// value of K
else
K++;
}
int P = abs(sum1 - sum2);
// Check if P is greater than K
// or if K-P is odd
if (P > K or (K - P) % 2) {
cout << 0;
return;
}
// Print the count of ways
cout << nCr(K, (P + K) / 2);
}
// Driver Code
int main()
{
string S1 = "1010";
string S2 = "10??";
countWays(S1, S2);
return 0;
}
Java
// Java program for above approach
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
class GFG{
// Function to find the factorial of
// the given number N
static int fact(int n)
{
// Stores the factorial
int res = 1;
// Iterate over the range [2, N]
for (int i = 2; i <= n; i++) {
res = res * i;
}
// Return the resultant result
return res;
}
// Function to find the number of ways
// of choosing r objects from n
// distinct objects
static int nCr(int n, int r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Function to find the number of ways
// to replace '?' in string t to get
// the same count of 0s and 1s in the
// string S and T
static void countWays(String s, String t)
{
int n = s.length();
int sum1 = 0, sum2 = 0, K = 0;
// Traverse the string s
for (int i = 0; i < n; i++) {
// If the current character
// is 1
if (s.charAt(i) == '1') {
// Update the value of
// the sum1
sum1++;
}
// Otherwise
else
sum1--;
}
int m = t.length();
// Traverse the string t
for (int i = 0; i < m; i++) {
// If the current character
// is 1, then update the
// value of sum2
if (t.charAt(i) == '1') {
sum2++;
}
// If the current character
// is 0
else if (t.charAt(i) == '0') {
sum2--;
}
// Otherwise, update the
// value of K
else
K++;
}
int P = Math.abs(sum1 - sum2);
// Check if P is greater than K
// or if K-P is odd
if ((P > K) || (K - P) % 2==1) {
System.out.println(0);
return;
}
// Print the count of ways
System.out.println(nCr(K, (P + K) / 2));
}
// Driver Code
public static void main(String[] args)
{
String S1 = "1010";
String S2 = "10??";
countWays(S1, S2);
}
}
// This code is contributed by hritikrommie.
Python3
# Python 3 program for the above approach # Function to find the factorial of # the given number N def fact(n): # Stores the factorial res = 1 # Iterate over the range [2, N] for i in range(2,n+1,1): res = res * i # Return the resultant result return res # Function to find the number of ways # of choosing r objects from n # distinct objects def nCr(n, r): return fact(n) // (fact(r) * fact(n - r)) # Function to find the number of ways # to replace '?' in string t to get # the same count of 0s and 1s in the # string S and T def countWays(s, t): n = len(s); sum1 = 0 sum2 = 0 K = 0 # Traverse the string s for i in range(n): # If the current character # is 1 if (s[i] == '1'): # Update the value of # the sum1 sum1 += 1 # Otherwise else: sum1 -= 1 m = len(t) # Traverse the string t for i in range(m): # If the current character # is 1, then update the # value of sum2 if (t[i] == '1'): sum2 += 1 # If the current character # is 0 elif (t[i] == '0'): sum2 -= 1 # Otherwise, update the # value of K else: K += 1 P = abs(sum1 - sum2) # Check if P is greater than K # or if K-P is odd if (P > K or (K - P) % 2): print(0) return # Print the count of ways print(nCr(K, (P + K) // 2)) # Driver Code if __name__ == '__main__': S1 = "1010" S2 = "10??" countWays(S1, S2) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the factorial of
// the given number N
static int fact(int n)
{
// Stores the factorial
int res = 1;
// Iterate over the range [2, N]
for (int i = 2; i <= n; i++) {
res = res * i;
}
// Return the resultant result
return res;
}
// Function to find the number of ways
// of choosing r objects from n
// distinct objects
static int nCr(int n, int r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Function to find the number of ways
// to replace '?' in string t to get
// the same count of 0s and 1s in the
// string S and T
static void countWays(string s, string t)
{
int n = s.Length;
int sum1 = 0, sum2 = 0, K = 0;
// Traverse the string s
for (int i = 0; i < n; i++) {
// If the current character
// is 1
if (s[i] == '1') {
// Update the value of
// the sum1
sum1++;
}
// Otherwise
else
sum1--;
}
int m = t.Length;
// Traverse the string t
for (int i = 0; i < m; i++) {
// If the current character
// is 1, then update the
// value of sum2
if (t[i] == '1') {
sum2++;
}
// If the current character
// is 0
else if (t[i] == '0') {
sum2--;
}
// Otherwise, update the
// value of K
else
K++;
}
int P = Math.Abs(sum1 - sum2);
// Check if P is greater than K
// or if K-P is odd
if ((P > K) || ((K - P) % 2) != 0) {
Console.WriteLine(0);
return;
}
// Print the count of ways
Console.WriteLine( nCr(K, (P + K) / 2));
}
// Driver code
static public void Main()
{
string S1 = "1010";
string S2 = "10??";
countWays(S1, S2);
}
}
// This code is contributed by target_2.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the factorial of
// the given number N
function fact(n)
{
// Stores the factorial
let res = 1;
// Iterate over the range [2, N]
for(let i = 2; i <= n; i++)
{
res = res * i;
}
// Return the resultant result
return res;
}
// Function to find the number of ways
// of choosing r objects from n
// distinct objects
function nCr(n, r)
{
return fact(n) / (fact(r) * fact(n - r));
}
// Function to find the number of ways
// to replace '?' in string t to get
// the same count of 0s and 1s in the
// string S and T
function countWays(s, t)
{
let n = s.length;
let sum1 = 0, sum2 = 0, K = 0;
// Traverse the string s
for(let i = 0; i < n; i++)
{
// If the current character
// is 1
if (s[i] == '1')
{
// Update the value of
// the sum1
sum1++;
}
// Otherwise
else
sum1--;
}
let m = t.length;
// Traverse the string t
for(let i = 0; i < m; i++)
{
// If the current character
// is 1, then update the
// value of sum2
if (t[i] == '1')
{
sum2++;
}
// If the current character
// is 0
else if (t[i] == '0')
{
sum2--;
}
// Otherwise, update the
// value of K
else
K++;
}
let P = Math.abs(sum1 - sum2);
// Check if P is greater than K
// or if K-P is odd
if (P > K || (K - P) % 2)
{
document.write(0);
return;
}
// Print the count of ways
document.write(nCr(K, (P + K) / 2));
}
// Driver Code
let S1 = "1010";
let S2 = "10??";
countWays(S1, S2);
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad de tiempo: O(max(N, M))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA