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.
