Patching Array
Hard · Greedy · Array · Greedy
Problem
You are given an array nums of positive integers, sorted in increasing order, and an integer n. You may patch the array by inserting any positive integers you like.
After patching, every integer from 1 to n must be the sum of some elements of the array, each element used at most once. Return the fewest patches needed.
Examples
Input: nums = [1,4], n = 7 Output: 1
With 1 and 4 you can make 1, 4 and 5. Adding 2 makes every value from 1 to 7.
Input: nums = [1,2,2], n = 5 Output: 0
1, 2, 3 (1 + 2), 4 (2 + 2) and 5 (1 + 2 + 2) can all be made already.
Input: nums = [3], n = 10 Output: 3
Patching 1, 2 and 4 makes every value up to 10; two patches cannot reach 10.
Constraints
- 1 <= len(nums) <= 1000
- 1 <= nums[i] <= 10^4
- nums is sorted in increasing order
- 1 <= n <= 2^31 - 1
Approaches
- Baseline: track every reachable sum up to n — time O((k + p) · n), space O(n)
Follow-up
What if the array is not sorted, or you only want the smallest value that cannot be made? The use cases cover both: sort first, then run the same scan, and stop at the first gap instead of patching it.
Related problems
Start free on Cariara · Coding problems · System design studio
