Breaking an Integer to get Maximum Product | method return x ^ a in log ( a ) time ; Method returns maximum product obtained by breaking N ; base case 2 = 1 + 1 ; base case 3 = 2 + 1 ; breaking based on mod with 3 ; If divides evenly , then break into all 3 ; If division gives mod as 1 , then break as 4 + power of 3 for remaining part ; If division gives mod as 2 , then break as 2 + power of 3 for remaining part ; Driver code to test above methods
def power ( x , a ) : NEW_LINE INDENT res = 1 NEW_LINE while ( a ) : NEW_LINE INDENT if ( a & 1 ) : NEW_LINE INDENT res = res * x NEW_LINE DEDENT x = x * x NEW_LINE a >>= 1 NEW_LINE DEDENT return res NEW_LINE DEDENT def breakInteger ( N ) : NEW_LINE INDENT if ( N == 2 ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT if ( N == 3 ) : NEW_LINE INDENT return 2 NEW_LINE DEDENT maxProduct = 0 NEW_LINE if ( N % 3 == 0 ) : NEW_LINE INDENT maxProduct = power ( 3 , int ( N / 3 ) ) NEW_LINE return maxProduct NEW_LINE DEDENT elif ( N % 3 == 1 ) : NEW_LINE INDENT maxProduct = 2 * 2 * power ( 3 , int ( N / 3 ) - 1 ) NEW_LINE return maxProduct NEW_LINE DEDENT elif ( N % 3 == 2 ) : NEW_LINE INDENT maxProduct = 2 * power ( 3 , int ( N / 3 ) ) NEW_LINE return maxProduct NEW_LINE DEDENT DEDENT maxProduct = breakInteger ( 10 ) NEW_LINE print ( maxProduct ) NEW_LINE