Decomposition of a number.

[MysticVegeta]

For eg:

1 + 1 + 1 + 1 = 4.
1 + 1 + 2 = 4
2 + 2 = 4
1 + 3 = 4
4 = 4.

Now I have to output the max product as a result of any decomposition:

like:

1 * 1 * 1 * 1 = 4
1 * 1 * 2 = 2
2 * 2 = 4
1 * 3 = 3
4 = 4

max product is 4 and I have to output the product % 10007

so 4 % 10007 = 4.

Most people did this using a while loop and some math. Unfortunately I lack that knowledge. Could someone please help me with both recursion and math way? Thanks a lot.

[wtd]

Recursion is the "math way."

[Andy]

no, its the dumb way =P

Notice that (x-2)*2 >= x for all x>=4, and that 3^2>2^3


this shows that inorder to obtain the largest product, you want as many 3s as possible without getting any 1s.
so if x mod 3 = 0, divide it up to all x/3 3s, if x mod 3 = 1, use (x - 4) / 3 and two 2s, and if x mod 3 = 2, use (x-2) / 3 3s, and one 2.

code:

#include <iostream> #include <cmath> using std::cout; using std::endl; int main() {     int x = 20;             if ((x % 3) == 0)                 cout << (int)(pow (3, x / 3)) % 10007 << endl;         else if ((x % 3) == 1)                 cout << (int)(pow (3, ((x - 4) / 3)) * 4) % 10007 << endl;         else                 cout << (int)(pow(3, x / 3) * 2) % 10007 << endl;         return 0; }

or

code:

#include <iostream> #include <cmath> int main() {         int x = 10;         std::cout << (int)(pow (3, (x - ((x % 3) % 2))/ 3) * ((x % 3) ? pow(2, 3 - (x % 3)): 1)) % 10007 << std::endl;         return 0; }

this should get you the largest product everytime

[Martin]

Andy wrote:

no, its the dumb way =P

Notice that (x-2)*2 >= x for all x>=4, and that 3^2>2^3


this shows that inorder to obtain the largest product, you want as many 3s as possible without getting any 1s.
so if x mod 3 = 0, divide it up to all x/3 3s, if x mod 3 = 1, use (x - 4) / 3 and two 2s, and if x % 3 = 2, use (x-2) % 3, and one 2.

Hey,

Can you go into a bit more depth here?

[zylum]

andy, do you do topcoder? if not, you should

[Andy]

zylum, i've been wanting to get into it for a while.. i guess i can give it a try over my next work term (starting at the end of august), hopefully that'll increase my chance of getting a co op job at google haha..

martin,
(x-2)*2 >= x for all x>=4 shows that if you have any number greater than 4, breaking it up to 2s will increase the product,

3+3=6=2+2+2 and 3^2>2^3, this shows, that if you have a 6, its better to break it up into 3s rather than 2s. so we want to break the number down to 3s.

but lets you say you have n mod 3 = 1, this means, you'll get (n-1)/3 3s, and a 1, but that 1 doesnt increase your product. since 3+1 = 4 = 2+2, and 2*2 > 3*1, when ever we have such a case, its better to break off two 2s, and the rest into 3s.

[MysticVegeta]

Andy wrote:

3+3=6=2+2+2 and 3^2>2^3, this shows, that if you have a 6, its better to break it up into 3s rather than 2s. so we want to break the number down to 3s.

wait a sec, dont you mean, breaking it up into 3s would make 2 * 2 * 2 = 8. but breaking it up into 2s would make 3 * 3 = 9. which is greater. Is that a typo or am I misunderstanding something?

[zylum]

MysticVegeta wrote:

Andy wrote:

3+3=6=2+2+2 and 3^2>2^3, this shows, that if you have a 6, its better to break it up into 3s rather than 2s. so we want to break the number down to 3s.

wait a sec, dont you mean, breaking it up into 3s would make 2 * 2 * 2 = 8. but breaking it up into 2s would make 3 * 3 = 9. which is greater. Is that a typo or am I misunderstanding something?

breaking into 3s means 3+3 = 6. note the 3s.

[MysticVegeta]

oh I thought into 3 numbers... 2 + 2 + 2.. sorry for the confusion, Thanks for the answer guys, if I needed to create this using recursion how would I do that? something like this:

code:

//Pseudo void solve (sum : int, n : int) if (sum == n) {      max = Math.max (max, current);      current = 1;      return; } for (int i = 0; i <= sum; i++) {        solve (sum, n + i);        current *= i; }

I dont really know what I am doing. Thanks again for the math solution.