Patching Array
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
nums = [1,3], n = 61With 2 patches [1,2,3], all numbers 1-6 can be formed.
nums = [1,2,4,13,43], n = 1002Initially, 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.
nums = [2,6,16,30], n = 503Starting 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
Ready to solve this problem?
Practice solo and sharpen your skills for technical interviews.