A traveling collector has a satchel that can carry a total weight of at most 5000 units. Given the weight of each trinket in the collection, determine the maximum number of trinkets that can be packed into the satchel without the combined weight exceeding the limit.
The first line contains an integer n, the number of trinkets.
The second line contains n space-separated integers, the weight of each trinket.
Print a single integer: the maximum number of trinkets that fit in the satchel.
Example 1
Input
3 100 200 150
Expected
3
Explanation
The three trinkets weigh 100, 200, and 150 units, totaling 450, which is well under the 5000 unit limit, so all three fit in the satchel.
Example 2
Input
4 1500 1500 1500 1500
Expected
3
Explanation
Sorting the four 1500-unit trinkets and adding them one at a time, the running total reaches 1500, 3000, then 4500 after three trinkets; adding a fourth would push the total to 6000, which exceeds the 5000 limit, so only 3 trinkets fit.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →