Umbrella

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
8 upvotes
Asked in companies
SamsungDisney + HotstarArcesium

Problem statement

You are given ‘N’ types of umbrellas, where each umbrella can shelter some number of people. Given the number of people each umbrella can shelter in the array “UMBRELLA”, you need to determine the minimum number of umbrellas required to cover exactly ‘M’ people with umbrellas.

Note -

You have an infinite number of umbrellas of each type.
If it is not possible to shelter exactly ‘M’ people then print -1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ denoting the number of elements in the array “UMBRELLA” and ‘M’ denoting the number of people required to cover with umbrellas.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of the array “UMBRELLA”.
Output Format : 
For each test case, print the minimum number of required umbrellas.

Print the output of each test case on a new line.
Note : 
You don’t need to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 10^3
1 <= UMBRELLA[i] <= 10^9
1 <= M <= 10^3

Where ‘T’ represents the number of test cases, ‘N’ represents the number of types of umbrellas, “UMBRELLA[i]” represents the number of people it can cover, and ‘M’ denotes the number of people to cover with umbrellas.

Time Limit: 1 sec
Sample Input 1 :
2
3 30
5 10 25
4 11
1 5 6 9
Sample Output 1 :
2
2
Explanation For Sample output 1:
For the first test case, we can use one umbrella of 25 people and one of 5 people.

For the second test case, we can use one umbrella of 6 people and one of 5 people.

Sample Input 2:

2
2 3
2 4
5 15
5 1 3 2 4
Sample output 2:
-1
5
Explanation For Sample output 2:
For the first test case, we cannot cover exactly 3 people using any subarray of given umbrella.

For the second test case, we can use all umbrellas and cover all 15 peoples.
Hint

Can you think of trying all possible options?

Approaches (3)
Brute Force

Approach: The idea here is to try every possible option and consider the minimum ans.


 We have two possible options: either we use the i-th umbrella to cover people or not. 


So, the recurrence for the above problem is:

minNumberOfUmbrellas(i, M) = min(minNumberOfUmbrellas(i - 1, M), 1+ minNumberOfUmbrellas(i, M - UMBRELLA[i])).

 

minNumberOfUmbrellas(i, M) represents the minimum number of umbrellas required to shelter M people with first i umbrellas.

 

If we skip the i-th umbrella then the sub-problem is the same as solving for minNumberOfUmbrellas(i - 1, M) - a minimum number of umbrellas required to shelter M people with the first i - 1 umbrella.

 

If we consider the i-th umbrella then the sub-problem is the same as solving for 1 + minNumberOfUmbrellas(i, M - UMBRELLA[i]) - a minimum number of umbrellas required to shelter M - UMBRELLA[i] people with first i umbrellas (since we have an infinite umbrella of i-th type). Since we are considering the i-th umbrella we add 1 to the sub-problem.
 

The algorithm is as follows:

  1. Declare a minNumberOfUmbrellas function with parameters i, M, UMBRELLA where i represents the index for the i-th umbrella we are taking, M is the required number of people to shelter and UMBRELLA is the array passed in the input.
    • If M equals 0, If the required number of people to shelter is 0 then we don’t require any umbrellas.
      • Return 0.
    • Else If i equals 0, then we don’t have any umbrellas left to shelter M people,
      • Return INF.
    • Declare an integer variable ANS.
    • Set ANS to minNumberOfUmbrellas(i - 1, M, UMBRELLA) i.e not considering the i-th coin.
    • If M >= UMBRELLA[i - 1],
      • Update ans to min(ans, 1 + minNumberOfUmbrellas(i - 1, M - UMBRELLA[i - 1])) i.e considering the i-th umbrella.
    • Return the ANS.
Time Complexity

O(2^N * M), where N is the number of types of umbrellas and M is the number of people to shelter with umbrellas.

 

Since at every step we have two options either we consider i-th umbrella or not. And in the worst case, we can have one umbrella for each of the M people. Hence the overall time complexity is O(2^N * M).

Space Complexity

O(N), where N is the number of types of umbrellas.

 

Since the recursive call stack can grow up to the order of N. Hence the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Umbrella
Full screen
Console