Lintcode: Wood Cut

Given n pieces of wood with length L[i] (integer array). Cut them into small pieces to guarantee you could have equal or more than k pieces with the same length. What is the longest length you can get from the n pieces of wood? Given L & k, return the maximum length of the small pieces.

Have you met this question in a real interview? 

Yes

Example

For L=[232, 124, 456], k=7, return 114.

Note

You couldn't cut wood into float length.

Challenge

O(n log Len), where Len is the longest length of the wood.

Tags Expand 

Binary Search

Initial thoughts:
s1: get the greatest common divisor or all common divisors;
s2: binary search divisor from common divisors to get k;
Well, totally wrong. Wood could be cut with remainder.

Reference:
http://algorithm.yuanbin.me/binary_search/wood_cut.html

Key: transform the problem into mathematical model first.

Assume the length of equal small pieces is l, then number of pieces  = sum(L[i] / l). O(n)
The maximum length  of small pieces ranges from 0 to max wood length. O(log(maxL))
We can use binary search to try lengths in range:

while start <= end:
    mid = start + end;
    if sum(mid) < k, end = mid - 1;
    else if sum(mid) >= k, start = mid + 1;
return start - 1;

Time: O(nlong(maxL))
Space: O(1)

Note: pay attention to the range of Integer: -2147483648 to 2147483647  (about two billions)
For problems with an array input, it's better to clarify the range of elements and the number of elements.

class Solution {
public:
    /** 
     *@param L: Given n pieces of wood with length L[i]
     *@param k: An integer
     *return: The maximum length of the small pieces.
     */
    int woodCut(vector<int> L, int k) {
        // write your code here
        //what if k <= 0
        //what if L.size == 0 or L[i] == 0:  then maxLen = 0, return 0
        long int maxLen = 0;
        for(int i = 0; i < L.size(); i++){
            if(L[i] > maxLen) maxLen = L[i];
        }
        if(maxLen == 0) return 0;
        long int start = 1;//start = 0 is not good which may be denominator
        long int end = maxLen;
        //binary search
        while(start <= end){
            long int mid = (start + end) / 2;
            long int sum = 0;
            // get pieces sum
            for(int i = 0; i < L.size(); i++){
                sum += L[i] / mid;
            }
            if(sum < k) end = mid - 1;
            else start = mid + 1;
        }
        return start - 1;
    }
};

Lintcode Second:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public: /** *@param L: Given n pieces of wood with length L[i] *@param k: An integer *return: The maximum length of the small pieces. */ //7:49 -- 8:17 //for array problem, ask for range both number and value int woodCut(vector<int> L, int k) { long int maxLen = 0; for(int i = 0; i < L.size(); i++){ if(L[i] > maxLen) maxLen = L[i]; } if(maxLen == 0) return 0; long int start = 1; // note: denominator cannot be 0 long int end = maxLen; while(start <= end){ long int mid = (start + end) / 2; long int sum = 0; for(int i = 0; i < L.size(); i++){ sum += L[i] / mid; } if(sum >= k) start = mid + 1; else end = mid - 1; } return end; } };