Given two binary strings S1 and S2 of size N and M respectively such that the string S2 also contains the character ‘?’, the task is to find the number of ways to replace ‘?’ in the string S2 such that the count of 0s and 1s in the string S2 is the same as in the string S1.
Examples:
Input: S1 = “1010”, S2 = “10??”
Output: 2
Explanation:
Following are the ways to replace ‘?’ in the string S2:
- Replace “??” in the string S2 with “01” modifies the string S2 = “1001”. Now the counts of 0s and 1s in both the strings S1 and S2 are the same.
- Replace “??” in the string S2 with “10” modifies the string S2 = “1010”. Now the counts of 0s and 1s in both the strings S1 and S2 are the same.
Therefore, the total number of ways is 2.
Input: S1 = “0000”, S2 = “??10?”
Output: 0
Approach: The given problem can be solved by using the concepts of Combinatorial. Follow the steps below to solve the problem:
- Initialize variables say, sum1 as 0, sum2 as 0 that stores the number of 0s and 1s in the given string S1 and S2.
- Initialize a variable, say as 0 that stores the total count of ways to replace ‘?’ in the string S2 satisfying the given criteria.
- Traverse the string S1, if the current character is 1, then increment the value of sum1 by 1. Otherwise, decrement the value of sum1 by 1.
- Traverse the string S2, if the current character is 1 then, increment the value of sum2 by 1 or if the current character is 0 then, decrement the value of sum2 by 1.
- Traverse the string t, if the current character is ‘+’ increment the value of sum2 by 1. Otherwise, increment the value of K by 1.
- Initialize a variable, say P that stores the absolute difference of sum1 and sum2.
- If the value of P is at least K or the value of (K – P) is odd, then there are no possible ways to replace ‘?’ and therefore print 0. Otherwise, print the value of KC(P+K)/2 as the resultant count of ways.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the factorial of// the given number Nint 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 objectsint 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 Tvoid 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 Codeint main(){ string S1 = "1010"; string S2 = "10??"; countWays(S1, S2); return 0;} |
Java
// Java program for above approachimport 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 Ndef 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 objectsdef 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 Tdef 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 Codeif __name__ == '__main__': S1 = "1010" S2 = "10??" countWays(S1, S2) # This code is contributed by ipg2016107. |
C#
// C# program for the above approachusing System;class GFG{ // Function to find the factorial of// the given number Nstatic 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 objectsstatic 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 Tstatic 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 codestatic 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 Nfunction 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 objectsfunction 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 Tfunction 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 Codelet S1 = "1010";let S2 = "10??";countWays(S1, S2);// This code is contributed by Potta Lokesh</script> |
Output:
2
Time Complexity: O(max(N, M))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
