Questions

from lintcode
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.

Notice
You couldn't cut wood into float length.
If you couldn't get >= k pieces, return 0.

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

Idea

In case you misunderstand the question like I did before. Let me clarify: it does not want ALL cut pieces to be the same length. It only wants no less than k number of pieces which have the same length. And it is okay to have some other wood pieces with various length.

Start guessing with binary search, if you can get enough pieces, try a larger length, as required by the question (find maximum). Else, try a smaller length. We all know that the smaller the length, the more pieces you can have.

public class Solution {
    /**
     * @param L: Given n pieces of wood with length L[i]
     * @param k: An integer
     * @return: The maximum length of the small pieces
     */
    public int woodCut(int[] L, int k) {
        // write your code here
        if (L.length == 0) return 0;
        int min = 1;
        int max = Integer.MAX_VALUE;

        while(min + 1 < max) {
            int guessedLength = min + (max - min) / 2;
            if (enoughPieces(L, k, guessedLength))
                // try a larger length
                min = guessedLength;
            else
                // try a smaller length
                max = guessedLength;
        }

        if (enoughPieces(L, k, max))
            return max;
        else if (enoughPieces(L, k, min))
            return min;
        else
            return 0;
    }

    private boolean enoughPieces(int[] l, int k, int guess) {
        int pieces = 0;
        for (int len: l) {
            pieces += len / guess;
        }
        return pieces >= k;
    }
}