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:

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

int[] products = newint[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:

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

Thursday, December 5, 2013

No. 51 - Next Number with Same Set of Digits


Problem: Reorder the digits of a number, in order to get the next number which is the least one that is greater than the input number. For example, the number 34724126 is the next number of 34722641 when reordering digits.
Analysis: When a digit in a number is swapped with a greater digit on its right side, the number becomes greater. For example, if the digit 3 in the number 34722641 is swapped with digit 7, the result is 74322641 which is greater than the original number. The remaining issue how to get least number which is greater than the original one.
Since we are going to get the least number after reordering digits, let’s find digits to be swapped on the right side. The first three digits on the right side of 34722641 are 641 which are decreasingly sorted. The two digits among them are swapped, the whole number will become less.
Let’s move on to the left digits. The next digit on the right side is 2, which is less than 6 and 4 on its right side. If the digit 2 is swapped with 6 or 4, the whole number will be become greater. Since we are going to keep the swapped number as less as possible, the digit 2 is swapped with 4, which is less one between 4 and 6. The number becomes 34724621.
Now 34724621 is greater than the original number 34722641, but it’s not the least one which is greater than 34722641. The three digits on the right side, 6, 2 and 1, should be increasingly sorted, in order to form the least number 34724126 among numbers which are greater than of 34722641.
The solution can be implemented with the following JAVA code:
publicstatic String getLeastGreaterNumber(String number) {
List<Character> decreasingChars = new ArrayList();
int firstDecreasing = getDecreasingChars(number, decreasingChars);

if(isGreatestNumber(firstDecreasing)) {
return"";
}

String prefix = "";
if(firstDecreasing > 1) {
prefix = number.substring(0, firstDecreasing - 1);
}

StringBuilder resultBuilder = new StringBuilder(prefix);
char target = number.charAt(firstDecreasing - 1);
char leastGreater = swapLeastGreater(decreasingChars, target);
resultBuilder.append(leastGreater);

Collections.sort(decreasingChars);
appendList(resultBuilder, decreasingChars);

return resultBuilder.toString();
}

When all digits are already increasingly sorted in the input number, the number itself is the greatest number with given digits. We should discuss with our interviewers what to return for this case during interviewers. Here we just return an empty string for this case.
When firstDecreasing is 0, it means all digits are increasingly sorted, and the input number is the greatest number with given digits, as listed in the following method isGreatestNumber.
privatestatic Boolean isGreatestNumber(int firstDecreasing) {
return firstDecreasing == 0;
}

The following method getDecreasingChars gets the longest sequence of decreasing digits on the right side of a number:
privatestaticint getDecreasingChars(String number, List<Character> decreasing) {
int firstDecreasing = number.length() - 1;
for(; firstDecreasing > 0; --firstDecreasing) {
char curChar = number.charAt(firstDecreasing);
char preChar = number.charAt(firstDecreasing - 1);
decreasing.add(curChar);

if(curChar > preChar) {
break;
}
}

return firstDecreasing;
}

The following method swapLeastGreater swaps the digit before the decreasing digits on the right side (target) and the least digit which is greater than target:
privatestaticchar swapLeastGreater(List<Character> chars, char target) {
Iterator it=chars.iterator();
char finding = '9';
while(it.hasNext()) {
char value = ((Character)it.next()).charValue();
if(value > target && value < finding) {
finding = value;
}
}

chars.remove(new Character(finding));
chars.add(new Character(target));

return finding;
}

The following method appendList appends characters from a list into a string builder:
privatestaticvoid appendList(StringBuilder str, List<Character> chars) {
Iterator it=chars.iterator();
while(it.hasNext()) {
char value = ((Character)it.next()).charValue();
str.append(value);
}
}

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

Extended Problem 1: Given a set of digits, please output all numbers permutated by the digits in increasing order. For example, if the input are five digits 1, 2, 3, 4, 5, the output are numbers from 12345, 12354, ..., to 54321 in increasing order.
Extended Problem 2: Given a number n, please out put all numbers with n bits of 1 in increasing order. For example, if the input is 3, the output are numbers 7, 11, 13, …
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.

Tuesday, December 3, 2013

No. 50 - Numbers Appearing Once


Problem: In an array, all numbers appear three times except one which only appears only once. Please find the unique number.

 Analysis: It is simpler if we modify the problem a little bit: Please find a unique number from an array where other numbers appear twice. We could solve this simplified problem with the XOR bitwise operation. If all numbers in the array are XORed, the result is the number appearing only once, since pairs of numbers get 0 when they are XORed.

 The strategy with XOR does not work since all numbers except one appear three times, since the XOR result of a triple of numbers is the number itself.

 Even though we could not solve the problem with XOR, we may still stick on the bitwise operations. A number appears three times, each bit (either 0 or 1) also appears three times. If every bit of numbers appearing three time is added, the sum of every bit should be multiple of 3.

 Supposing every bit of numbers (including the unique number) in the input array is added. If the sum of a bit is multiple of 3, the corresponding bit in the unique number is 0. Otherwise, it is 1.

 The solution can be implemented in Java as the code listed below:

 publicstaticint FindNumberAppearingOnce(int[] numbers) {
int[] bitSum = newint[32];
for(int i = 0; i < 32; ++i) {
bitSum[i] = 0;
}

for(int i = 0; i < numbers.length; ++i) {
int bitMask = 1;
for(int j = 31; j >= 0; --j) {
int bit = numbers[i] & bitMask;
if(bit != 0) {
bitSum[j] += 1;
}

bitMask = bitMask << 1;
}
}

int result = 0;
for(int i = 0; i < 32; ++i) {
result = result << 1;
result += bitSum[i] % 3;
}

return result;
}

 The time efficiency of this solution is O(n), and space efficiency is O(1) because an array with 32 elements is created. It's more efficient than two straightforward solutions: (1) It's easy to find the unique number from a sorted array, but it costs O(nlogn) time to sort an array with n elements. (2) We may utilize a hash table to store the number of occurrences of each element in the array, but the cost for the hash table is O(n).

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

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.
Subscribe to: Posts (Atom)

AltStyle によって変換されたページ (->オリジナル) /