I only completed an online assessment, which had a mix of DSA and core subjects.

After the online assessment, selected candidates were called to the main office for the next interview process.

The coding problem I received was on Dynamic Programming (DP), while all my friends had BFS or DFS questions.

Problem Statement:

You are tasked with determining the minimum number of umbrellas required to shelter a given number of people exactly, using umbrellas of various sizes. If it is not possible to meet the exact requirement using any combination of the available umbrella sizes, return -1.

Inputs:

1. requirement (integer): The total number of people needing shelter.
2. sizes (list of integers): A list of umbrella sizes, where each size represents the number of people an umbrella can shelter.

Output:

Return the minimum number of umbrellas needed to shelter exactly the given number of people (requirement). If it is not possible to achieve the exact requirement, return -1.

Example 1:

Input: requirement = 5 sizes = [3, 5]

Explanation: A single umbrella of size 5 can exactly shelter 5 people.

Output: 1