Tuesday, December 17, 2013

No. 52 - Maximal Product when Cutting Rope

Problem: Given a rope with length n, how to cut the rope into m parts with length n[0], n[1], ..., n[m-1], in order to get the maximal product of n[0]*n[1]* ... *n[m-1]? We have to cut once at least. Additionally, the length of the whole length of the rope, as well as the length of each part, are in integer value.

For example, if the length of the rope is 8, the maximal product of the part lengths is 18. In order to get the maximal product, the rope is cut into three parts with lengths 2, 3, and 3 respectively.

Analysis: There are two solutions to solve this problem. One is the traditional dynamic programming solution with O(n2) time and O(n) space, and the other is a quite creative and efficient solution with O(1) time and O(1) space.

Solution 1: Dynamic programming

Firstly let’s define a function f(n) for the maximal length product after cutting a rope with length n into parts. We have n-1 choice for the first cut on the rope, with the length of the first part 1, 2, … n-1 respectively. Therefore, f(n)=max(f(i)*f(n-i), where 0<i<n).

If the equation is resolved recursively in top-down order, there are lots of overlapping sub-problems and it’s a waste of recalculation.  It’s much more efficient to calculate in bottom-up order. That is to say, we firstly get f(2), and then f(3), then f(4), f(5). We continue till we get f(n).

The following Java code solves the problem in bottom-up order:

public static int maxProductAfterCutting_solution1(int length) {
    if(length < 2) {
        return 0;
    }
    if(length == 2) {
        return 1;
    }
    if(length == 3) {
        return 2;
    }

    int[] products = new int[length + 1];
    products[0] = 0;
    products[1] = 1;
    products[2] = 2;
    products[3] = 3;

    for(int i = 4; i <= length; ++i) {
        int max = 0;
        for(int j = 1; j <= i / 2; ++j) {
            int product = products[j] * products[i - j];
            if(max < product) {
                max = product;
            }

            products[i] = max;
        }
    }

    return products[length];
}

An array products with length n+1 is created, in order to store the maximal product of for ropes with length 0, 1, 2, …, n.

Solution 2: Tricky cutting strategy

There is a strategy to cut the rope to get maximal product: We cut the parts with length either 3 or 2. Additionally, we try to keeping cut parts with length 3 as many as possible. Therefore, we could solve the problem with the following Java code:

public static int maxProductAfterCutting_solution2(int length) {
    if(length < 2) {
        return 0;
    }
    if(length == 2) {
        return 1;
    }
    if(length == 3) {
        return 2;
    }

    int timesOf3 = length / 3;
    if((length - timesOf3 * 3) % 2 == 1) {
        timesOf3 -= 1;
    }

    int timesOf2 = (length - timesOf3 * 3) / 2;

    return (int)(Math.pow(3, timesOf3)) * (int)(Math.pow(2, timesOf2));
}

This solution sounds a bit tricky, and it does not make sense if we can’t prove it mathematically. Let’s try to demonstrate its correctness.

When n≥5, we could prove that 2(n-2)>n and 3(n-3)>n. Therefore, we continue to cut rope into parts with length 3 or 2 when the length is greater than 5. Additionally, 3(n-3) ≥ 2(n-2) when n≥5, so we cut parts with length 3 as many as possible.

The prerequisite of the proof above is n≥5. How about n is 4? There are only two approaches to cut when the length of the rope is 4: Cut into two parts with lengths 1 and 3, or with lengths 2 and 2. In our strategy, the rope will be cut into two parts with length 2 and 2. The other approach is discarded because a part with length 1 is not allowed. Notice that 4=2*2, and 2*2>1*3. That’s to say, it’s no harm to cut a rope with length 4 into two parts with same length 2.

Therefore, our strategy to cut ropes is correct.

Code with unit tests is shared at http://ideone.com/wGvr86.

More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

16 comments:

  1. Is the proof for Approach 2 complete? What if n>=5 and get 4 first? You didn't proove 4(n-4) is not optimal.

    ReplyDelete
    Replies
    1. Hi Harry,

      Your writing shines like gold! There is no room for gibberish here clearly. You nailed it in Maximal Product when Cutting Rope!

      I need something where I can run iis, sql server express and an application server to deploy a program. I thought I could use LightSail but I don't see an option to install the application server. Should I be using something else?

      S3 with this, one can retrieve the key information which is occupied in creating cloud structural design and amount of produced information also can be stored in this component that is the consequence of the key specified.

      Anyways great write up, your efforts are much appreciated.

      Best Regards,
      Kevin

      Delete
  2. Likely related to your 2nd solution, the pattern of numbers seems to follow the formula: product[len] = max( product[len-2] * 2, product[len-3] * 3 ). Using this formula an O(n) time and O(1) space algorithm is possible.

    ReplyDelete
  3. If the length of the rope is 7, then cutting it into {3,3,1} yields a product of 9, whereas there exists an option {5,2} that yields a product of 10.

    ReplyDelete
    Replies
    1. Tarik,
      You should never cut a length of 1 since this does not increase the resulting product. The optimal solution is 3*2*2 = 12, which Harry's method would give.

      Delete
  4. Another way to see the proof of method 2 is using basic calculus to optimize the function f(m) = (n/m)^m, where m is the number of pieces. A simple symmetry argument shows that each piece should be the same length. Using logarithmic differentiation you find that f is maximized when m=n/e. This means that the length of each piece is should be n/m=e~2.71. Since we must use integral lengths, monotonicity of the function f then implies that the optimal solution occurs when n/m =3 as much as possible.

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. Nice blog Harry. Found useful.

    I cracked Amazon,India. Request seekers to go through some material..
    http://ashayraut.wordpress.com/interview-preparation-best-100/

    ReplyDelete
  7. Its simply superb.Feeling good to share the link to practice here is the link c# interview questions @ http://skillgun.com

    ReplyDelete
  8. Harry, thank you for such an useful blog. Great contribution! Can you explain why in solution#1, products[3] = 3?

    ReplyDelete
  9. Analogica Data is one of best product developement company in india,developing a product means developing a bond with your clients and businesses. The strength of the relationship depends on the functionality and Product Development Service Provider
    .

    ReplyDelete
  10. This is among the posts that i have seen to be very interesting, I never knew that cutting a rope could involve such measures. This is a very humorous post, a page that i am glad to have com across. If you buy a very beautiful Nest Chandelier Light, you will make the lighting in your house more elegant and classy.Kindly check our link and find out more on the same.

    ReplyDelete
  11. if n = 10, m = 2
    The code does not match the title.

    ReplyDelete
  12. Got a question about how to write a programmer resume or need more samples? Feel free to contact me! computer programming resume

    ReplyDelete
  13. Hey Brother,

    Seems like I won the lottery here….This is a treasure box of blogs and your folks are like leprechauns! Phenomenal read on No. 52 - Maximal Product when Cutting Rope

    We have a t2.micro instance (built from amzn-ami-hvm-2016.09.1.20170119-x86_64-gp2) on which a customized WordPress is deployed. Following various posts here and elsewhere, various parameters for Apache and MySQL have been set to accommodate the 'size' of the host, AWS Tutorial including the deployment of a swap partition. The site has been running without issue for weeks.

    Please keep providing such valuable information.

    Shukran,

    Irene Hynes

    ReplyDelete
  14. Hi There,


    Grazie! Grazie! Grazie! Your blog is indeed quite interesting around No. 52 - Maximal Product when Cutting Rope I agree with you on lot of points!

    Why is it so difficult to cancel services on AWS?
    I am looking around to find way to cancel but there is no link anywhere. AWS Tutorial

    It is highly pathetic because we know that you can make it easy because you know how to do it.
    I am not sure if it is on purpose.
    But let me know how to cancel my services and pleas give right information.





    Follow my new blog if you interested in just tag along me in any social media platforms!


    Gracias
    Ajeeth

    ReplyDelete