588. Patch the Gaps
A vending machine accepts coins whose values are listed in the sorted array nums; each listed coin is available exactly once. A customer should be able to pay any whole amount from 1 to n using some subset of the coins (no change is given).
The owner may add extra coins of any positive integer value to the machine, and each added coin is also usable at most once. Return the minimum number of extra coins that must be added so that every amount in [1, n] can be paid exactly. The array is non-decreasing and may contain repeated values. The intended solution runs in O(m + log n) time and O(1) space, where m = nums.length.
Example 1
- Input:
- nums = [2,3], n = 8
- Output:
- 2
- Explanation:
Adding a coin of value 1 and another of value 2 lets the coins 1, 2, 2, 3 pay every amount from 1 to 8, and one extra coin alone is not enough.
Example 2
- Input:
- nums = [1,5,10], n = 20
- Output:
- 2
- Explanation:
Coins 2 and 4 are added so that 1, 2, 4, 5, 10 reach every amount up to 22, covering 1 to 20.
Example 3
- Input:
- nums = [1,2,4,8], n = 15
- Output:
- 0
- Explanation:
The coins already form every amount from 1 to 15, so no extra coin is needed.
Constraints
- 1 ≤ nums.length ≤ 105
- 1 ≤ nums[i] ≤ 109, and nums is sorted in non-decreasing order
- 1 ≤ n ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(m + log n)
- Space
- O(1)