Probability such that two subset contains same number of elements | Java implementation of the above approach ; Returns value of Binomial Coefficient C ( n , k ) ; Since C ( n , k ) = C ( n , n - k ) ; Calculate value of ; Iterative Function to calculate ( x ^ y ) in O ( log y ) ; Initialize result ; If y is odd , multiply x with result ; y must be even now y = y / 2 ; Change x to x ^ 2 ; Recursive function to return gcd of a and b ; Function to find probability ; Calculate total possible ways and favourable ways . ; Divide by gcd such that they become relatively coprime ; Driver code
class GFG { static int binomialCoeff ( int n , int k ) { int res = 1 ; if ( k > n - k ) k = n - k ; for ( int i = 0 ; i < k ; ++ i ) { res *= ( n - i ) ; res /= ( i + 1 ) ; } return res ; } static int power ( int x , int y ) { int res = 1 ; while ( y > 0 ) { if ( ( y & 1 ) == 1 ) res = res * x ; y = y >> 1 ; x = x * x ; } return res ; } static int gcd ( int a , int b ) { if ( b == 0 ) return a ; return gcd ( b , a % b ) ; } static void FindProbability ( int n ) { int up = binomialCoeff ( 2 * n , n ) ; int down = power ( 2 , 2 * n ) ; int g = gcd ( up , down ) ; up /= g ; down /= g ; System . out . println ( up + " / " + down ) ; } public static void main ( String [ ] args ) { int N = 8 ; FindProbability ( N ) ; } }