Count ways to replace ' ? ' in a Binary String to make the count of 0 s and 1 s same as that of another string | Java program for 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
import java . util . ArrayList ; import java . util . Arrays ; import java . util . HashMap ; import java . util . Map ; class GFG { static int fact ( int n ) { int res = 1 ; for ( int i = 2 ; i <= n ; i ++ ) { res = res * i ; } return res ; } static int nCr ( int n , int r ) { return fact ( n ) / ( fact ( r ) * fact ( n - r ) ) ; } static 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 . charAt ( i ) == '1' ) { sum1 ++ ; } else sum1 -- ; } int m = t . length ( ) ; for ( int i = 0 ; i < m ; i ++ ) { if ( t . charAt ( i ) == '1' ) { sum2 ++ ; } else if ( t . charAt ( i ) == '0' ) { sum2 -- ; } else K ++ ; } int P = Math . abs ( sum1 - sum2 ) ; if ( ( P > K ) || ( K - P ) % 2 == 1 ) { System . out . println ( 0 ) ; return ; } System . out . println ( nCr ( K , ( P + K ) / 2 ) ) ; } public static void main ( String [ ] args ) { String S1 = "1010" ; String S2 = "10 ? ? " ; countWays ( S1 , S2 ) ; } }