Minimum size binary string required such that probability of deleting two 1 's at random is 1/X | Python3 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
from math import sqrt NEW_LINE def MinimumString ( x ) : NEW_LINE INDENT b = 1 NEW_LINE left_lim = sqrt ( x ) + 1.0 NEW_LINE right_lim = sqrt ( x ) + 2.0 NEW_LINE for i in range ( int ( left_lim ) , int ( right_lim ) + 1 ) : NEW_LINE INDENT if ( i > left_lim and i < right_lim ) : NEW_LINE INDENT r = i NEW_LINE break NEW_LINE DEDENT DEDENT return b + r NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT X = 2 NEW_LINE print ( MinimumString ( X ) ) NEW_LINE DEDENT