# Breaking an Integer to get Maximum Product

Given an number n, the task is to broken in such a way that multiplication of its parts is maximized.

```Input : n = 10
Output : 36
10 = 4 + 3 + 3 and 4 * 3 * 3 = 36
is maximum possible product.

Input : n = 8
Output : 18
8 = 2 + 3 + 3 and 2 * 3 * 3 = 36
is maximum possible product.
```

Mathematically, we are given n and we need to maximize a1 * a2 * a3 …. * aK such that n = a1 + a2 + a3 … + aK and a1, a2, … ak > 0.

Note that we need to break given Integer in at least two parts in this problem for maximizing the product.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Now we know from maxima-minima concept that, If an integer need to break in two parts, then to maximize their product those part should be equal. Using this concept lets break n into (n/x) x’s then their product will be x(n/x), now if we take derivative of this product and make that equal to 0 for maxima, we will get to know that value of x should be e (base of the natural logarithm) for maximum product. As we know that 2 < e < 3, so we should break every Integer into 2 or 3 only for maximum product.
Next thing is 6 = 3 + 3 = 2 + 2 + 2, but 3 * 3 > 2 * 2 * 2, that is every triplet of 2 can be replaced with tuple of 3 for maximum product, so we will keep breaking the number in terms of 3 only, until number remains as 4 or 2, which we will be broken into 2*2 (2*2 > 3*1) and 2 respectively and we will get our maximum product.
In short, procedure to get maximum product is as follows – Try to break integer in power of 3 only and when integer remains small (<5) then use brute force.
The complexity of below program is O(log N), because of repeated squaring power method.

Below is the implementation of above approach:

## C++

 `// C/C++ program to find maximum product by breaking ` `// the Integer ` `#include ` `using` `namespace` `std; ` ` `  `// method return x^a in log(a) time ` `int` `power(``int` `x, ``int` `a) ` `{ ` `    ``int` `res = 1; ` `    ``while` `(a) ` `    ``{ ` `        ``if` `(a & 1) ` `            ``res = res * x; ` `        ``x = x * x; ` `        ``a >>= 1; ` `    ``} ` `    ``return` `res; ` `} ` ` `  `// Method returns maximum product obtained by ` `// breaking N ` `int` `breakInteger(``int` `N) ` `{ ` `    ``//  base case 2 = 1 + 1 ` `    ``if` `(N == 2) ` `        ``return` `1; ` ` `  `    ``//  base case 3 = 2 + 1 ` `    ``if` `(N == 3) ` `        ``return` `2; ` ` `  `    ``int` `maxProduct; ` ` `  `    ``//  breaking based on mod with 3 ` `    ``switch` `(N % 3) ` `    ``{ ` `        ``// If divides evenly, then break into all 3 ` `        ``case` `0: ` `            ``maxProduct = power(3, N/3); ` `            ``break``; ` ` `  `        ``// If division gives mod as 1, then break as ` `        ``// 4 + power of 3 for remaining part ` `        ``case` `1: ` `            ``maxProduct = 2 * 2 * power(3, (N/3) - 1); ` `            ``break``; ` ` `  `        ``// If division gives mod as 2, then break as ` `        ``// 2 + power of 3 for remaining part ` `        ``case` `2: ` `            ``maxProduct = 2 * power(3, N/3); ` `            ``break``; ` `    ``} ` `    ``return` `maxProduct; ` `} ` ` `  `//  Driver code to test above methods ` `int` `main() ` `{ ` `    ``int` `maxProduct = breakInteger(10); ` `    ``cout << maxProduct << endl; ` `    ``return` `0; ` `} `

## Java

 `// Java program to find maximum product by breaking ` `// the Integer ` ` `  `class` `GFG{ ` `// method return x^a in log(a) time ` `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; ` `} ` ` `  `// Method returns maximum product obtained by ` `// breaking N ` `static` `int` `breakInteger(``int` `N) ` `{ ` `    ``// base case 2 = 1 + 1 ` `    ``if` `(N == ``2``) ` `        ``return` `1``; ` ` `  `    ``// base case 3 = 2 + 1 ` `    ``if` `(N == ``3``) ` `        ``return` `2``; ` ` `  `    ``int` `maxProduct=-``1``; ` ` `  `    ``// breaking based on mod with 3 ` `    ``switch` `(N % ``3``) ` `    ``{ ` `        ``// If divides evenly, then break into all 3 ` `        ``case` `0``: ` `            ``maxProduct = power(``3``, N/``3``); ` `            ``break``; ` ` `  `        ``// If division gives mod as 1, then break as ` `        ``// 4 + power of 3 for remaining part ` `        ``case` `1``: ` `            ``maxProduct = ``2` `* ``2` `* power(``3``, (N/``3``) - ``1``); ` `            ``break``; ` ` `  `        ``// If division gives mod as 2, then break as ` `        ``// 2 + power of 3 for remaining part ` `        ``case` `2``: ` `            ``maxProduct = ``2` `* power(``3``, N/``3``); ` `            ``break``; ` `    ``} ` `    ``return` `maxProduct; ` `} ` ` `  `// Driver code to test above methods ` `public` `static` `void` `main(String[] args) ` `{ ` `    ``int` `maxProduct = breakInteger(``10``); ` `    ``System.out.println(maxProduct); ` `} ` `} ` `// This code is contributed by mits `

/div>

## Python3

 `# Python3 program to find maximum product by breaking  ` `# the Integer  ` `   `  `# method return x^a in log(a) time  ` `def` `power(x, a):  ` `  `  `    ``res ``=` `1``;  ` `    ``while` `(a): ` `        ``if` `(a & ``1``):  ` `            ``res ``=` `res ``*` `x;  ` `        ``x ``=` `x ``*` `x;  ` `        ``a >>``=` `1``; ` `         `  `    ``return` `res;  ` `   `  `# Method returns maximum product obtained by  ` `# breaking N  ` `def` `breakInteger(N): ` `    ``#  base case 2 = 1 + 1  ` `    ``if` `(N ``=``=` `2``):  ` `        ``return` `1``;  ` `   `  `    ``#  base case 3 = 2 + 1  ` `    ``if` `(N ``=``=` `3``):  ` `        ``return` `2``;  ` `   `  `    ``maxProduct``=``0``;  ` `   `  `    ``#  breaking based on mod with 3  ` `    ``if``(N ``%` `3``=``=``0``):  ` `        ``# If divides evenly, then break into all 3  ` `        ``maxProduct ``=` `power(``3``, ``int``(N``/``3``));  ` `        ``return` `maxProduct;  ` `    ``elif``(N``%``3``=``=``1``): ` `        ``# If division gives mod as 1, then break as  ` `        ``# 4 + power of 3 for remaining part  ` `        ``maxProduct ``=` `2` `*` `2` `*` `power(``3``, ``int``(N``/``3``) ``-` `1``);  ` `        ``return` `maxProduct; ` `    ``elif``(N``%``3``=``=``2``): ` `        ``# If division gives mod as 2, then break as  ` `        ``# 2 + power of 3 for remaining part ` `        ``maxProduct ``=` `2` `*` `power(``3``, ``int``(N``/``3``)); ` `        ``return` `maxProduct; ` `      `  `   `  `#  Driver code to test above methods  ` ` `  `  `  `maxProduct ``=` `breakInteger(``10``);  ` `print``(maxProduct);  ` `     `  `# This code is contributed by mits `

## C#

 `// C# program to find maximum product by breaking  ` `// the Integer  ` ` `  `class` `GFG{  ` `// method return x^a in log(a) time  ` `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;  ` `}  ` ` `  `// Method returns maximum product obtained by  ` `// breaking N  ` `static` `int` `breakInteger(``int` `N)  ` `{  ` `    ``// base case 2 = 1 + 1  ` `    ``if` `(N == 2)  ` `        ``return` `1;  ` ` `  `    ``// base case 3 = 2 + 1  ` `    ``if` `(N == 3)  ` `        ``return` `2;  ` ` `  `    ``int` `maxProduct=-1;  ` ` `  `    ``// breaking based on mod with 3  ` `    ``switch` `(N % 3)  ` `    ``{  ` `        ``// If divides evenly, then break into all 3  ` `        ``case` `0:  ` `            ``maxProduct = power(3, N/3);  ` `            ``break``;  ` ` `  `        ``// If division gives mod as 1, then break as  ` `        ``// 4 + power of 3 for remaining part  ` `        ``case` `1:  ` `            ``maxProduct = 2 * 2 * power(3, (N/3) - 1);  ` `            ``break``;  ` ` `  `        ``// If division gives mod as 2, then break as  ` `        ``// 2 + power of 3 for remaining part  ` `        ``case` `2:  ` `            ``maxProduct = 2 * power(3, N/3);  ` `            ``break``;  ` `    ``}  ` `    ``return` `maxProduct;  ` `}  ` ` `  `// Driver code to test above methods  ` `public` `static` `void` `Main()  ` `{  ` `    ``int` `maxProduct = breakInteger(10);  ` `    ``System.Console.WriteLine(maxProduct);  ` `}  ` `}  ` `// This code is contributed by mits  `

## PHP

 `>= 1;  ` `    ``}  ` `    ``return` `\$res``;  ` `}  ` `   `  `// Method returns maximum product obtained by  ` `// breaking N  ` `function` `breakInteger(``\$N``)  ` `{  ` `    ``//  base case 2 = 1 + 1  ` `    ``if` `(``\$N` `== 2)  ` `        ``return` `1;  ` `   `  `    ``//  base case 3 = 2 + 1  ` `    ``if` `(``\$N` `== 3)  ` `        ``return` `2;  ` `   `  `    ``\$maxProduct``=0;  ` `   `  `    ``//  breaking based on mod with 3  ` `    ``switch` `(``\$N` `% 3)  ` `    ``{  ` `        ``// If divides evenly, then break into all 3  ` `        ``case` `0:  ` `            ``\$maxProduct` `= power(3, ``\$N``/3);  ` `            ``break``;  ` `   `  `        ``// If division gives mod as 1, then break as  ` `        ``// 4 + power of 3 for remaining part  ` `        ``case` `1:  ` `            ``\$maxProduct` `= 2 * 2 * power(3, (``\$N``/3) - 1);  ` `            ``break``;  ` `   `  `        ``// If division gives mod as 2, then break as  ` `        ``// 2 + power of 3 for remaining part  ` `        ``case` `2:  ` `            ``\$maxProduct` `= 2 * power(3, ``\$N``/3);  ` `            ``break``;  ` `    ``}  ` `    ``return` `\$maxProduct``;  ` `}  ` `   `  `//  Driver code to test above methods  ` ` `  `  `  `    ``\$maxProduct` `= breakInteger(10);  ` `    ``echo` `\$maxProduct``;  ` `     `  `// This code is contributed by mits ` `?> `

Output:

```36
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## tags:

Mathematical Mathematical