Patching Array
Given a sorted integer array nums and an integer n, add or patch elements to the array such that any number in the range [1, n] inclusive can be formed by the sum of some elements in the array.
Return the minimum number of patches required.
Example 1
Input
nums = [1,3], n = 6Output
1Adding 2 lets the possible sums cover every number in the range [1, 6], so only 1 patch is needed.
Example 2
Input
nums = [1,5,10], n = 20Output
2The two patches can be [2, 4].
Constraints
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 10^4
- nums is sorted in ascending order.
- 1 <= n <= 2^31 - 1