Description
Given a sorted integer array nums and an integer n, add/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.
Examples
Input:
nums = [1,3], n = 6Output:
1Explanation:
With 2 patches [1,2,3], all numbers 1-6 can be formed.
Input:
nums = [1,2,4,13,43], n = 100Output:
2Explanation:
Initially, coverage spans [1,7] with existing elements. Patching 8 extends coverage to [1,15]. Adding 13 reaches [1,28]. Patching 29 extends to [1,57]. With 43, coverage reaches [1,100]. Total patches needed: 2.
Input:
nums = [2,6,16,30], n = 50Output:
3Explanation:
Starting with coverage [0,0]. Since 1 cannot be formed, patching 1 gives coverage [1,1]. Adding 2 extends to [1,3]. Since 4 cannot be formed, patching 4 gives coverage [1,7]. Adding 6 extends to [1,13]. Total patches: 2.
Constraints
- •
1 ≤ nums.length ≤ 1000 - •
1 ≤ nums[i] ≤ 10⁴ - •
1 ≤ n ≤ 2³¹ - 1