Length of smallest sequence having sum X and product Y | Python3 program for the above approach ; Function for checking valid or not ; Function for checking boundary of binary search ; Function to calculate the minimum sequence size using binary search ; Initialize high and low ; Base case ; Print - 1 if a sequence cannot be generated ; Otherwise ; Iterate until difference between high and low exceeds 1 ; Calculate mid ; Reset values of high and low accordingly ; Print the answer ; Driver Code ; Function call
from math import floor , exp NEW_LINE def temp ( n , x ) : NEW_LINE INDENT return pow ( x * 1 / n , n ) NEW_LINE DEDENT def check ( n , y , x ) : NEW_LINE INDENT v = temp ( n , x ) NEW_LINE return ( v >= y ) NEW_LINE DEDENT def find ( x , y ) : NEW_LINE INDENT high = floor ( x / exp ( 1.0 ) ) NEW_LINE low = 1 NEW_LINE if ( x == y ) : NEW_LINE INDENT print ( 1 ) NEW_LINE DEDENT elif ( not check ( high , y , x ) ) : NEW_LINE INDENT print ( - 1 ) NEW_LINE DEDENT else : NEW_LINE INDENT while ( high - low > 1 ) : NEW_LINE INDENT mid = ( high + low ) // 2 NEW_LINE if ( check ( mid , y , x ) ) : NEW_LINE INDENT high = mid NEW_LINE DEDENT else : NEW_LINE INDENT low = mid NEW_LINE DEDENT DEDENT print ( high ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT x = 9 NEW_LINE y = 8 NEW_LINE find ( x , y ) NEW_LINE DEDENT