hardGreedyPure DSA~30 min
Fewest Patches to Cover Every Amount
A payment system can sum any subset of a sorted list of denomination chips to make a total. You may add extra chips. Find the fewest additions so every amount from 1 to n is achievable.
Problem
Given a sorted array nums of positive integers and an integer n, add the minimum number of extra positive integers (patches) so that every value in the range [1, n] can be formed as the sum of some subset of the resulting array. Return the minimum number of patches required.
Input
A sorted array nums of positive integers and an integer n.
Output
An integer: the minimum number of patches.
Constraints
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 10^4, nums is sorted ascending
- 1 <= n <= 2^31 - 1
Examples
Example 1
Input
nums = [1,3], n = 6
Output
1
Adding 2 lets you form every value in [1,6].
Example 2
Input
nums = [1,5,10], n = 20
Output
2
Adding 2 and 4 covers the whole range.