Minimum Umbrellas Problem
You are provided with ‘N’ types of umbrellas, where each umbrella type can shelter a certain number of people. Given an array UMBRELLA
that indicates the number of people each umbrella can cover, determine the minimum number of umbrellas required to shelter exactly ‘M’ people.
Input:
T
N M
UMBRELLA
Output:
Minimum number of umbrellas or -1
Example:
Input:
2
3 5
2 3 4
4 7
1 3 5 6
Output:
2
2
Explanation:
In the first test case, using one 2-capacity umbrella and one 3-capacity umbrella gives a total of 5 people covered. In the second test case, using one 6-capacity umbrella and one 1-capacity umbrella covers exactly 7 people.
Constraints:
1 ≤ T ≤ 5
1 ≤ N ≤ 103
1 ≤ UMBRELLA[i] ≤ 109
1 ≤ M ≤ 103
Note:
If it is not feasible to cover ‘M’ people exactly, print -1.
Ensure you implement the function provided and do not handle input/output operations directly.
Given 'N' types of umbrellas with different capacities, find the minimum number of umbrellas required to shelter exactly 'M' people.
Iterate through the umbrella capacities and try to cover 'M' people ...read more
Top Apple Software Developer Intern interview questions & answers
Popular interview questions of Software Developer Intern
Reviews
Interviews
Salaries
Users/Month