Count ways to replace ' ? ' in a Binary String to make the count of 0 s and 1 s same as that of another string | 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
def fact ( n ) : NEW_LINE INDENT res = 1 NEW_LINE for i in range ( 2 , n + 1 , 1 ) : NEW_LINE INDENT res = res * i NEW_LINE DEDENT return res NEW_LINE DEDENT def nCr ( n , r ) : NEW_LINE INDENT return fact ( n ) // ( fact ( r ) * fact ( n - r ) ) NEW_LINE DEDENT def countWays ( s , t ) : NEW_LINE INDENT n = len ( s ) ; NEW_LINE sum1 = 0 NEW_LINE sum2 = 0 NEW_LINE K = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( s [ i ] == '1' ) : NEW_LINE INDENT sum1 += 1 NEW_LINE DEDENT else : NEW_LINE INDENT sum1 -= 1 NEW_LINE DEDENT DEDENT m = len ( t ) NEW_LINE for i in range ( m ) : NEW_LINE INDENT if ( t [ i ] == '1' ) : NEW_LINE INDENT sum2 += 1 NEW_LINE DEDENT elif ( t [ i ] == '0' ) : NEW_LINE INDENT sum2 -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT K += 1 NEW_LINE DEDENT DEDENT P = abs ( sum1 - sum2 ) NEW_LINE if ( P > K or ( K - P ) % 2 ) : NEW_LINE INDENT print ( 0 ) NEW_LINE return NEW_LINE DEDENT print ( nCr ( K , ( P + K ) // 2 ) ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT S1 = "1010" NEW_LINE S2 = "10 ? ? " NEW_LINE countWays ( S1 , S2 ) NEW_LINE DEDENT