dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: Given two numbers, return max product

  1. #1
    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. #2
    Join Date
    Jul 2013
    Posts
    576

    Re: Given two numbers, return max product

    Quote Originally Posted by X_Coder View Post
    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. #3
    Join Date
    Feb 2015
    Posts
    3

    Re: Given two numbers, return max product

    But i need write it on DP.

  4. #4
    Join Date
    Jul 2013
    Posts
    576

    Re: Given two numbers, return max product

    Quote Originally Posted by X_Coder View Post
    But i need write it on DP.
    What's DP?

    Something important you forgot to mention in your first post?

  5. #5
    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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  6. #6
    Join Date
    Feb 2015
    Posts
    3

    Re: Given two numbers, return max product

    Quote Originally Posted by laserlight View Post
    I would guess "Dynamic Programming", but that is just a guess.
    Yes i'm sorry that is dynamic programming!

  7. #7
    Join Date
    Jul 2013
    Posts
    576

    Re: Given two numbers, return max product

    Quote Originally Posted by X_Coder View Post
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)