Given a number of people N and an array of integers, each one representing the amount of people a type of umbrella can handle, output the minimum number of umbrellas needed to handle N people.
No umbrella could have left spaces. Which means if a umbrella can handle 2 people, there should be 2 people under it.
If there's no solution, return -1
.
solve(3, [1, 2])
means that we have 3 people and two kinds of umbrellas, one that hanled one person and one that handles 2.
We can give one two-sized umbrella to 2 of them and the other to the last person. Therefore the solution is 2
(umbrellas).
You could give 3 one-sized umbrellas, but we want the minimum number.
solve(10, [3, 1])
. You can give 3 three-sized umbrellas and 1 one-sized. This means the solution is 4
.
solve(3, [2])
. There's no solution since one umbrella would have empty space. Return -1
.
Java solution
private static int getMinCount(int[] arr, int n) {
if (arr == null || arr.length == 0 || n < 1)
return -1;
int i = arr.length - 1;
Arrays.sort(arr);
int count = 0;
while (n >= 0 && i >= 0) {
count += n / arr[i];
n = n % arr[i];
i--;
}
return n != 0 ? -1 : count;
}