# 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<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>=k;
}

}


## 2 Answers

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

I have added a getMaxValue() method to limit the search?

Could you please evaluate the solution if is it meets the limiting the search ?

Thanks.

package main.algorithms;

public class CutWood {

public boolean isValid(int[] wood, int cutLength, int k){
int count = 0;
for(int w: wood){
count += w / cutLength;
}
return count >= k;
}

public int cutWood(int[] wood, int k){
// corner cases:
if(wood.length == 0 || k == 0) return 0;
int left = 1;
int right = getMaxValue(wood);
int res = 0;

if(!isValid(wood, left, k)) return 0;

while(left < right){
int mid = left + (right - left)/2;
boolean valid = isValid(wood, mid, k);
if(valid){
left = mid + 1;
res = mid;
}
else
right = mid;
}
return res;
}

private int getMaxValue(int[] wood) {
int max = 0;
for(int i : wood){
if (i> max){
max  = i;
}
}
return max;
}

}