Problem 7: Given an integer( up to100). Find the maximum product.
Sample Input: 7
Sample Output: 12
7 = 7 ( product = 7)
7 = 6 + 1( product = 6*1 = 6)
7 = 5 + 2(product = 5*2 = 10)
7 = 2 + 3 + 2 ( product = 2*3*2 = 12)
so maximum product is 12
Solution: How can we solve this ? First, we can try to divide the number into various part then calculate the product. But again problem here. How many ways we can divide a number and how can we do this. For an example, we can divide 10 in many ways... 5+5, 2+2+3+3, 3+3+3+1, .... then what is the solution ?
What is the maximum product for 1, i think you get it. it's 1. So, save the result into an array.
int Result[102];
Result[1] = 1;
What is the result for 2, it's 2. ( 2 itself ), Set Result[2] = 2;
For 3,
3 ( product = 3)
1 + 2 ( product = 1*2 = 2)
Set Result[3] = 3;
Now consider 4, we can make 4 in the following ways:
4 = 1 + 3 = Result[1] * Result[3] = 1*3 = 3
We already know the result of 1 and 3 from the Result array
4 = 2 + 2 = Result[2] * Result[2] = 2*2 = 4
4 itself = 4
So maximum product = 4, and set Result[4] = 4.
Similarly, for 5,
5 = 5 itself,
5 = 1 + 4 ( Result[1] * Result[4] = 1*4 = 4)
5 = 2 + 3 ( Result[2] * Result[3] = 2*3 = 6)
maximum product = 6
Calculate the remaining number in the same fashion.
Note: Result will not fit in 32 bit integer, use 64 bit integer array.
Source Code: Here
Back to Problem list