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.

AnswerBot
2d

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

Help your peers!
Add answer anonymously...
Apple Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter