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
< ? php function power ( $ x , $ a ) { $ res = 1 ; while ( $ a ) { if ( $ a & 1 ) $ res = $ res * $ x ; $ x = $ x * $ x ; $ a >>= 1 ; } return $ res ; } function breakInteger ( $ N ) { if ( $ N == 2 ) return 1 ; if ( $ N == 3 ) return 2 ; $ maxProduct = 0 ; switch ( $ N % 3 ) { case 0 : $ maxProduct = power ( 3 , $ N / 3 ) ; break ; case 1 : $ maxProduct = 2 * 2 * power ( 3 , ( $ N / 3 ) - 1 ) ; break ; case 2 : $ maxProduct = 2 * power ( 3 , $ N / 3 ) ; break ; } return $ maxProduct ; } $ maxProduct = breakInteger ( 10 ) ; echo $ maxProduct ; ? >