Breaking an Integer to get Maximum Product | Java program to find maximum product by breaking the Integer ; 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
class GFG { static int power ( int x , int a ) { int res = 1 ; while ( a > 0 ) { if ( ( a & 1 ) > 0 ) res = res * x ; x = x * x ; a >>= 1 ; } return res ; } static int breakInteger ( int N ) { if ( N == 2 ) return 1 ; if ( N == 3 ) return 2 ; int maxProduct = - 1 ; 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 ; } public static void main ( String [ ] args ) { int maxProduct = breakInteger ( 10 ) ; System . out . println ( maxProduct ) ; } }