Changyeong and Coffee
InterviewTime limit2sMemory limit512 MB
Given N coffee cups with caffeine amounts, find the minimum number of cups whose contents sum to exactly K, or -1 if impossible.
- Level
Easy3 of 10
- Topics
- Dynamic programming, Array, Greedy, Brute force
- Solved
- No attempts yet
Problem
Changyeong likes coffee. He arrives at the office and wants to enjoy his morning coffee.
The office has N coffees, each prepared as a single cup, and each coffee has a caffeine content Ci.
Changyeong wants to choose some of the N coffees so that he consumes exactly K caffeine.
What is the minimum number of coffees Changyeong must drink to consume exactly K caffeine?
Input
The first line gives the number of coffees N and the amount of caffeine Changyeong must consume K.
The second line gives the caffeine contents Ci of the N coffees.
Output
Print the minimum number of coffees Changyeong must drink to consume K caffeine.
If he cannot drink exactly K caffeine, print -1.
Constraints
- 1 ≤ N ≤ 100
- 0 ≤ K ≤ 100,000
- 1 ≤ Ci ≤ 1,000
Hint
Note that only one cup of each type of coffee is prepared, so the same coffee cannot be drunk more than once.