Minimum size binary string required such that probability of deleting two 1 's at random is 1/X | C ++ implementation of the above approach ; Function returns the minimum size of the string ; From formula ; Left limit of r ; Right limit of r ; Smallest integer in the valid range ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int MinimumString ( int x ) { int b = 1 ; double left_lim = sqrt ( x ) + 1.0 ; double right_lim = sqrt ( x ) + 2.0 ; int r ; for ( int i = left_lim ; i <= right_lim ; i ++ ) { if ( i > left_lim and i < right_lim ) { r = i ; break ; } } return b + r ; } int main ( ) { int X = 2 ; cout << MinimumString ( X ) ; return 0 ; }