
February 3rd, 2015, 12:44 AM
#1
Given two numbers, return max product
I was asked this question, and I'd like to know how others would solve it. I'm most comfortable with C++, but solutions in other languages are welcome.
You must divide the number n into m parts without changing the order of digits and the product obtained by m numbers has to be maximum.
Input: 12345 3
Output: 2460
I must implement it on "dynamic programming".
Last edited by X_Coder; February 3rd, 2015 at 01:23 PM.

February 3rd, 2015, 05:04 AM
#2
Re: Given two numbers, return max product
Originally Posted by X_Coder
I'd like to know how others would solve it.
If the input number (or rather ndigit sequence) isn't too long and there isn't any complexity requirements, I would simply generate all valid splits of the number and then pick the one(s) with the biggest product.
There are n1 possible split positions and m1 of these are selected in each split. That's the equivalent of finding all (m1)subsets of an (n1)set. There are many algorithms for this but I would use the so called Gosper's hack which works on integer bitsets (effectively restricting my solution to n<64).
In your example we are looking for all 2subsets of a 4set. These are,
0011
0101
0110
1001
1010
1100
where the 1's represent the split positions. Performing these splits yields,
123*4*5 = 2460 (winner)
12*34*5 = 2040
12*3*45 = 1620
1*234*5 = 1170
1*23*45 = 1035
1*2*345 = 690
What I have suggest is an exhaustive solution that grows exponentially with m and n and so quite quickly becomes intractable. But it's not unthinkable it could be formulated as an optimization problem which, with a little bit of luck, may provide a shortcut that may find a solution in polynominal time.
Last edited by razzle; February 4th, 2015 at 01:17 AM.

February 3rd, 2015, 07:39 AM
#3
Re: Given two numbers, return max product
But i need write it on DP.

February 3rd, 2015, 11:40 AM
#4
Re: Given two numbers, return max product
Originally Posted by X_Coder
But i need write it on DP.
What's DP?
Something important you forgot to mention in your first post?

February 3rd, 2015, 12:43 PM
#5
Re: Given two numbers, return max product
I would guess "Dynamic Programming", but that is just a guess.

February 3rd, 2015, 01:22 PM
#6
Re: Given two numbers, return max product
Originally Posted by laserlight
I would guess "Dynamic Programming", but that is just a guess.
Yes i'm sorry that is dynamic programming!

February 4th, 2015, 01:26 AM
#7
Re: Given two numbers, return max product
Originally Posted by X_Coder
Yes i'm sorry that is dynamic programming!
So you're not interested in different ways to solve this problem right. It's just ordinary homework you want someone else to do for you. Next time state all premises up front.
I hope you're not expecting people to post fully implemented solutions for you to cherrypick from. That would be cheating. Instead show what you have and where you're stuck and someone may help you.
Last edited by razzle; February 5th, 2015 at 06:17 AM.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
