Question

Formatted question description: https://leetcode.ca/all/330.html

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] <= 10⁴
nums is sorted in ascending order.
1 <= n <= 2³¹ - 1

Algorithm

We define a variable miss to represent the smallest unrepresentable value between [0,n], then initialize it to 1,

Why is it not 0? Because n=0 is meaningless, it returns 0 directly.

Then the range we can represent at this time is [0, miss), which means that we can represent the number from 0 to miss-1 at this time. If num <= miss at this time, then we can expand the range of numbers we can represent to [0, miss+num), if num>miss, then we need to add a number at this time, in order to maximize the range of the number, we add miss itself, and so on until we traverse the entire array, we can got the answer.

Let us give an example to illustrate:

Given nums = [1, 2, 4, 11, 30], n = 50, we need to make all the numbers between [0, 50] be represented by the sum of the numbers in nums.

First, using 1, 2, 4 may represent all the numbers between 0 and 7, the range is [0, 8), but we cannot represent 8, because the next number 11 is too big, so we have to add it to the array An 8, the range that can be represented at this time is [0, 16), then do we need to insert 16, the answer is no, because our array has 1 and 4, which can form 5, and the next number 11 can be combined together 16, so with the 11 in the array, the range we can represent at this time is expanded to [0, 27), but we can’t represent 27, because 30 is too big, so we add 27 to the array at this time, then Now the range that can be represented is [0, 54), which has already met the requirements. We have added two numbers 8 and 27 in total, so return 2.

Code

public class Patching_Array {

    public static void main(String[] args) {
        Patching_Array out = new Patching_Array();
        Solution s = out.new Solution();

        System.out.println(s.minPatches(new int[]{1, 2, 4, 11, 30}, 50));
    }

    class Solution {
        public int minPatches(int[] nums, int n) {

            long miss = 1;
            int res = 0, i = 0;

            while (miss <= n) {
                if (i < nums.length && nums[i] <= miss) {
                    miss += nums[i++];
                } else {
                    miss += miss;
                    ++res;
                }
            }
            return res;

        }
    }
}

class Solution {
public:
    bool isValidSerialization(string preorder) {
        istringstream in(preorder);
        vector<string> v;
        string t = "";
        int cnt = 0;
        while (getline(in, t, ',')) v.push_back(t);
        for (int i = 0; i < v.size() - 1; ++i) {
            if (v[i] == "#") {
                if (cnt == 0) return false;
                --cnt;
            } else ++cnt;
        }
        return cnt == 0 && v.back() == "#";
    }
};

//////////

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int capacity = 1;
        preorder += ",";
        for (int i = 0; i < preorder.size(); ++i) {
            if (preorder[i] != ',') continue;
            if (--capacity < 0) return false;
            if (preorder[i - 1] != '#') capacity += 2;
        }
        return capacity == 0;
    }
};

class Solution(object):
  def minPatches(self, nums, n):
    """
    :type nums: List[int]
    :type n: int
    :rtype: int
    """
    i = 0
    patches = 0
    miss = 1
    while miss <= n:
      if i < len(nums) and nums[i] <= miss:
        miss += nums[i]
        i += 1
      else:
        miss += miss
        patches += 1
    return patches

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
}

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;
}

330 - Patching Array

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions