Breaking an Integer to get Maximum Product | C / C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int power ( int x , int a ) { int res = 1 ; while ( a ) { if ( a & 1 ) res = res * x ; x = x * x ; a >>= 1 ; } return res ; } int breakInteger ( int N ) { if ( N == 2 ) return 1 ; if ( N == 3 ) return 2 ; int maxProduct ; 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 ; } int main ( ) { int maxProduct = breakInteger ( 10 ) ; cout << maxProduct << endl ; return 0 ; }