Count ways to replace ' ? ' in a Binary String to make the count of 0 s and 1 s same as that of another string | C ++ program for the above approach ; Function to find the factorial of the given number N ; Stores the factorial ; Iterate over the range [ 2 , N ] ; Return the resultant result ; Function to find the number of ways of choosing r objects from n distinct objects ; Function to find the number of ways to replace ' ? ' in string t to get the same count of 0 s and 1 s in the string S and T ; Traverse the string s ; If the current character is 1 ; Update the value of the sum1 ; Otherwise ; Traverse the string t ; If the current character is 1 , then update the value of sum2 ; If the current character is 0 ; Otherwise , update the value of K ; Check if P is greater than K or if K - P is odd ; Print the count of ways ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int fact ( int n ) { int res = 1 ; for ( int i = 2 ; i <= n ; i ++ ) { res = res * i ; } return res ; } int nCr ( int n , int r ) { return fact ( n ) / ( fact ( r ) * fact ( n - r ) ) ; } void countWays ( string s , string t ) { int n = s . length ( ) ; int sum1 = 0 , sum2 = 0 , K = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( s [ i ] == '1' ) { sum1 ++ ; } else sum1 -- ; } int m = t . length ( ) ; for ( int i = 0 ; i < m ; i ++ ) { if ( t [ i ] == '1' ) { sum2 ++ ; } else if ( t [ i ] == '0' ) { sum2 -- ; } else K ++ ; } int P = abs ( sum1 - sum2 ) ; if ( P > K or ( K - P ) % 2 ) { cout << 0 ; return ; } cout << nCr ( K , ( P + K ) / 2 ) ; } int main ( ) { string S1 = "1010" ; string S2 = "10 ? ? " ; countWays ( S1 , S2 ) ; return 0 ; }