CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Given two numbers, return max product

1. Junior Member
Join Date
Feb 2015
Posts
3

## 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.

2. Member +
Join Date
Jul 2013
Posts
576

## 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 n-digit 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 n-1 possible split positions and m-1 of these are selected in each split. That's the equivalent of finding all (m-1)-subsets of an (n-1)-set. There are many algorithms for this but I would use the so called Gosper's hack which works on integer bit-sets (effectively restricting my solution to n<64).

In your example we are looking for all 2-subsets of a 4-set. 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 short-cut that may find a solution in polynominal time.
Last edited by razzle; February 4th, 2015 at 01:17 AM.

3. Junior Member
Join Date
Feb 2015
Posts
3

## Re: Given two numbers, return max product

But i need write it on DP.

4. Member +
Join Date
Jul 2013
Posts
576

## 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?

5. Elite Member Power Poster
Join Date
Jan 2006
Location
Singapore
Posts
6,768

## Re: Given two numbers, return max product

I would guess "Dynamic Programming", but that is just a guess.

6. Junior Member
Join Date
Feb 2015
Posts
3

## 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!

7. Member +
Join Date
Jul 2013
Posts
576

## 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 cherry-pick 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
•