Skip to content

330. 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.

 

Example 1:

Input: nums = [1,3], n = 6
Output: 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

Example 2:

Input: nums = [1,5,10], n = 20
Output: 2
Explanation: The two patches can be [2, 4].

Example 3:

Input: nums = [1,2,2], n = 5
Output: 0

 

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 104
  • nums is sorted in ascending order.
  • 1 <= n <= 231 - 1

Solutions

Solution 1: Greedy

Let's assume that the number \(x\) is the smallest positive integer that cannot be represented. Then all the numbers in \([1,..x-1]\) can be represented. In order to represent the number \(x\), we need to add a number that is less than or equal to \(x\):

  • If the added number equals \(x\), since all numbers in \([1,..x-1]\) can be represented, after adding \(x\), all numbers in the range \([1,..2x-1]\) can be represented, and the smallest positive integer that cannot be represented becomes \(2x\).
  • If the added number is less than \(x\), let's assume it's \(x'\), since all numbers in \([1,..x-1]\) can be represented, after adding \(x'\), all numbers in the range \([1,..x+x'-1]\) can be represented, and the smallest positive integer that cannot be represented becomes \(x+x' \lt 2x\).

Therefore, we should greedily add the number \(x\) to cover a larger range.

We use a variable \(x\) to record the current smallest positive integer that cannot be represented, initialized to \(1\). At this time, \([1,..x-1]\) is empty, indicating that no number can be covered; we use a variable \(i\) to record the current index of the array being traversed.

We perform the following operations in a loop:

  • If \(i\) is within the range of the array and \(nums[i] \le x\), it means that the current number can be covered, so we add the value of \(nums[i]\) to \(x\), and increment \(i\) by \(1\).
  • Otherwise, it means that \(x\) is not covered, so we need to supplement a number \(x\) in the array, and then update \(x\) to \(2x\).
  • Repeat the above operations until the value of \(x\) is greater than \(n\).

The final answer is the number of supplemented numbers.

The time complexity is \(O(m + \log n)\), where \(m\) is the length of the array \(nums\). The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minPatches(self, nums: List[int], n: int) -> int:
        x = 1
        ans = i = 0
        while x <= n:
            if i < len(nums) and nums[i] <= x:
                x += nums[i]
                i += 1
            else:
                ans += 1
                x <<= 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int minPatches(int[] nums, int n) {
        long x = 1;
        int ans = 0;
        for (int i = 0; x <= n;) {
            if (i < nums.length && nums[i] <= x) {
                x += nums[i++];
            } else {
                ++ans;
                x <<= 1;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long long x = 1;
        int ans = 0;
        for (int i = 0; x <= n;) {
            if (i < nums.size() && nums[i] <= x) {
                x += nums[i++];
            } else {
                ++ans;
                x <<= 1;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func minPatches(nums []int, n int) (ans int) {
    x := 1
    for i := 0; x <= n; {
        if i < len(nums) && nums[i] <= x {
            x += nums[i]
            i++
        } else {
            ans++
            x <<= 1
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function minPatches(nums: number[], n: number): number {
    let x = 1;
    let ans = 0;
    for (let i = 0; x <= n; ) {
        if (i < nums.length && nums[i] <= x) {
            x += nums[i++];
        } else {
            ++ans;
            x *= 2;
        }
    }
    return ans;
}

Comments