Probability such that two subset contains same number of elements | C ++ 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 ; Function to find probability ; Calculate total possible ways and favourable ways . ; Divide by gcd such that they become relatively coprime ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; 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 ; } int power ( int x , unsigned int y ) { int res = 1 ; while ( y > 0 ) { if ( y & 1 ) res = res * x ; y = y >> 1 ; x = x * x ; } return res ; } 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 ; cout << up << " / " << down << endl ; } int main ( ) { int N = 8 ; FindProbability ( N ) ; return 0 ; }