Cut Wood / Facebook Interview This question was asked through the Facebook interview and the suggested solution is solving via binary search.

I have put the binary search solution but it still looks too complicated.

Question:


  Given an int array wood representing the length of n pieces of wood and an int k. It is required to cut these pieces of wood such that more or equal to
  k pieces of the same length len are cut. What is the longest len you can get?


Input: wood = [5, 9, 7], k = 3
    Output: 5
    Explanation:
    5 -> 5
    9 -> 5 + 4
    7 -> 5 + 2

Input: wood = [5, 9, 7], k = 4
Output: 4
Explanation:
5 -> 4 + 1
9 -> 4 * 2 + 1
7 -> 4 + 3

package AmazonOthers.src;

import java.util.Arrays;

public class CutWood {


    public static void main(String[] args) {
        int[] array1 = {5,9,7};
        int k = 3;
        System.out.println( woodCut(array1,k) ) ;

        int[] array2 = {124,232,456};
        Arrays.sort(array2);
        int k2 = 7;
        System.out.println( woodCut(array2,k2) ) ;

        int[] array3 = {3,6,7,11};
        Arrays.sort(array3);
        int k3 = 8;
        System.out.println( woodCut(array3,k3) ) ;

    }

    private static int woodCut(int[] array1,int k) {

        int l = 0;
        int h = Integer.MAX_VALUE;

        while(l&lt;h){
            int mid = l + (h-l)/2;
            if(isValid(array1, mid, k)){
                l = mid +1;
            }else{
                h=mid-1;
            }
        }
        return h;

    }

    private static boolean isValid(int[] array1, int mid, int k) {

        int count = 0;
        for(int val: array1){
            count+=val/mid;
        }
        return count&gt;=k;
    }


}
Overall I think you have about the simplest you could hope for. The only thing I'd do is set your bounds better. You know that you can do min(array)/ceil(k/len(array)) and you know you at most you can do max(array)/floor(k/len(array)).

I was going to suggest going for extra credit with a more sophisticated algorithm, but I don't think you can beat what the binary search approach. At worst you're going to be 32 or 64 * O(n). Given the simplicity of the algorithm I think that will likely beat sorting and all the alternatives I can think of either explicitly or implicitly do a sort which would be O(n log n).