330

330. Patching Array (Hard)

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

Companies: Amazon, Snowflake, Google

Related Topics:
Array, Greedy

Similar Questions:

• Maximum Number of Consecutive Values You Can Make (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/patching-array
// Author: github.com/lzl124631x
// Time: O(L + sqrt(N)) where L is the length of A
// Space: O(1)
// Ref: https://discuss.leetcode.com/topic/35494/solution-explanation
class Solution {
public:
    int minPatches(vector<int>& A, int n) {
        long miss = 1, ans = 0, i = 0, N = A.size(); // miss is the next missing number
        while (miss <= n) { // keep looping while miss <= n
            if (i < N && A[i] <= miss) miss += A[i++]; // if the current missing number is covered, extend miss by A[i] and increment i
            else {
                miss += miss; // if miss is not covered, patch miss. Extend miss by miss, and increment answer.
                ++ans;
            }
        }
        return ans;
    }
};

Or

// OJ: https://leetcode.com/problems/patching-array
// Author: github.com/lzl124631x
// Time: O(L + sqrt(N)) where L is the length of A
// Space: O(1)
class Solution {
public:
    int minPatches(vector<int>& A, int n) {
        long i = 0, ans = 0, miss = 1, N = A.size();
        while (true) {
            while (i < N && A[i] <= miss) miss += A[i++]; // keep consuming A[i] until we find the next missing number
            if (miss > n) break; // break if the missing number > n
            ++ans; // patch miss
            miss += miss;
        }
        return ans;
    }
};