Leetcode 330 - Patching Array

https://leetcode.com/problems/patching-array/

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in 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:
nums = [1, 3], n = 6
Return 1.

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:
nums = [1, 5, 10], n = 20
Return 2.
The two patches can be [2, 4].

Example 3:
nums = [1, 2, 2], n = 5
Return 0.

https://leetcode.com/discuss/82822/solution-explanation

think about nums = [1,1,1,1,...]. Then you'll go through all those before you ever get to doubling. It's O(k+log(n)), where k is the size of the array.

int minPatches(vector<int>& nums, int n) {
    long miss = 1, added = 0, i = 0;
    while (miss <= n) {
        if (i < nums.size() && nums[i] <= miss) {
            miss += nums[i++];
        } else {
            miss += miss;
            added++;
        }
    }
    return added;
}

Let miss be the smallest sum in [1,n] that we might be missing. Meaning we already know we can build all sums in [1,miss). Then if we have a number num <= miss in the given array, we can add it to those smaller sums to build all sums in [1,miss+num). If we don't, then we must add such a number to the array, and it's best to add miss itself, to maximize the reach.

Another implementation, though I prefer the above one.

int minPatches(vector<int>& nums, int n) {
    int count = 0, i = 0;
    for (long miss=1; miss <= n; count++)
        miss += (i < nums.size() && nums[i] <= miss) ? nums[i++] : miss;
    return count - i;
}

https://discuss.leetcode.com/topic/35709/share-my-thinking-process

The question asked for the "minimum number of patches required". In other words, it asked for an optimal solution. Lots of problems involving optimal solution can be solved by dynamic programming and/or greedy algorithm. I started with greedy algorithm which is conceptually easy to design. Typically, a greedy algorithm needs selection of best moves for a subproblem. So what is our best move?

Think about this example: nums = [1, 2, 3, 9]. We naturally want to iterate through nums from left to right and see what we would discover. After we encountered 1, we know 1...1 is patched completely. After encountered 2, we know 1...3 (1+2) is patched completely. After we encountered 3, we know 1...6 (1+2+3) is patched completely. After we encountered 9, the smallest number we can get is 9. So we must patch a new number here so that we don't miss 7, 8. To have 7, the numbers we can patch is 1, 2, 3 ... 7. Any number greater than 7 won't help here. Patching 8 will not help you get 7. So we have 7 numbers (1...7) to choose from. I hope you can see number 7 works best here because if we chose number 7, we can move all the way up to 1+2+3+7 = 13. (1...13 is patched completely) and it makes us reach n as quickly as possible. After we patched 7 and reach 13, we can consider last element 9 in nums. Having 9 makes us reach 13+9 = 22, which means 1...22 is completely patched. If we still did't reach n, we can then patch 23, which makes 1...45 (22+23) completely patched. We continue until we reach n.

    public int minPatches(int[] nums, int n) {
        if (n <= 0) return 0;
        nums = nums == null ? new int[0] : nums;
        int current_ind = 0, ret = 0;
        long boundary_val = 1, sum = 0;
        while (boundary_val <= n) {
            if (current_ind < nums.length && nums[current_ind] <= boundary_val) {
                sum += nums[current_ind++];
                boundary_val = sum + 1;
            } else {
                ret++;
                sum += boundary_val;
                boundary_val = sum + 1;
            }
        }
        return ret;
    }

https://leetcode.com/discuss/82827/o-log-n-time-o-1-space-java-with-explanation-trying-my-best
https://leetcode.com/discuss/82832/java-here-is-my-greedy-version-with-brief-explanations-1ms

Greedy idea: add the maximum possible element whenever there is a gap

Iterating the nums[], and keeps adding them up, and we are getting a running sum. At any position, if nums[i] > sum+1, them we are sure we have to patch a sum+1 because all nums before index i can't make sum+1 even add all of them up, and all nums after index i are all simply too large.

public class Solution {
    public int minPatches(int[] nums, int n) {
        long sum = 0;
        int count = 0;
        for (int x : nums) {
            if (sum >= n) break;
            while (sum+1 < x && sum < n) { 
                ++count;
                sum += sum+1;
            }
            sum += x;
        }
        while (sum < n) {
            sum += sum+1;
            ++count;
        }
        return count;
    }
}

http://bookshadow.com/weblog/2016/01/27/leetcode-patching-array/

假设数组nums的“部分元素和”可以表示范围[1, total)内的所有数字，

那么向nums中添加元素add可以将表示范围扩充至[1, total + add)，其中add ≤ total，当且仅当add = total时取到范围上界[1, 2 * total)

若nums数组为空，则构造[1, n]的nums为[1, 2, 4, 8, ..., k]，k为小于等于n的2的幂的最大值。

若nums数组非空，则扩展时利用nums中的已有元素，详见代码。

    def minPatches(self, nums, n):
        """
        :type nums: List[int]
        :type n: int
        :rtype: int
        """
        idx, total, ans = 0, 1, 0
        size = len(nums)
        while total <= n:
            if idx < size and nums[idx] <= total:
                total += nums[idx]
                idx += 1
            else:
                total <<= 1
                ans += 1
        return ans

https://www.hrwhisper.me/leetcode-patching-array/

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

        int cnt = 0,i=0;

        for(long known_sum = 1;known_sum <= n;){

            if(i < nums.length && known_sum >= nums[i]){

                known_sum += nums[i++];

            }else{

                known_sum <<= 1;

                cnt++;

            }

        }

        return cnt;

    }

http://www.zrzahid.com/patching-array/

Basically, as long as cumulative sum so far is greater than the number we need to create , we are good. But id cumsum falls below the current number (between 1 to n) we need to create , then we have to add the current cumsum to itself (why?). This is because we assumed at any particular time cumsum is equal or greater than the current element we need to create. That is we doubling the cumsum when we add a missing element.

public static int minPatches(int[] nums, int n) {
 int sum = 1;
 int i = 0;
 int count = 0;
 
 while(sum <= n){
  if(i < nums.length && nums[i] <= sum){
   sum+=nums[i++];
  }
  else{
   sum<<=1;
   count++;
  }
 }
 
 return count;
}

Google 2016 面试题 | 数组补丁

给出一个从小到大排好序的整数数组nums和一个整数n，在数组中添加若干个补丁（元素）使得[1,n]的区间内的所有数都可以表示成nums中若干个数的和。返回最少需要添加的补丁个数。

Example 1：
nums = [1, 3], n = 6

返回1，表示至少需要添加1个数｛2｝，才可以表示1到6之间所有数。

Example 2:
nums = [1, 5, 10], n = 20

返回2，表示至少需要添加两个数｛2，4｝，才可以表示1到20之间所有数。

读者不难想到暴力搜索的做法：先穷举每一个不在数组里的数p，再穷举判断p是否可以表示为数组中若干个数的和；如果不能，则把p加入数组中，把答案加一。

然而，这种做法时间复杂度高且实际操作难度大（需要考虑穷举的顺序）。我们不妨先思考一个简单的问题，如果nums数组为空，那么最少需要多少个数字才能表示1到n之间所有数？相信大家都可以想到一个贪心算法，即按照1、2、4、8...都顺序添加，每次加入都数都比之前所有数的总和大1，直到总和大于n。本题的难点是预先给出了一些数，但这不影响我们的贪心策略：假设nums当前至多可以表示1到m之间的所有数，加入m+1；直到m大于等于n。

此题的最优算法是贪心。在实际面试过程中，笔者认为只需要想到贪心算法，并给出算法框架，就可以达到hire的程度。能在短时间内完成程序，可以达到strong hire。

    public int minPatches(int[] nums, int n) {
        long sum = 0;
        int ans = 0;
        int index = 0;
        if (nums.length > 0 && nums[0] == 1) {
            sum = 1;
            index = 1;
        }
        while (sum < n)
        {
            while (index < nums.length && nums[index] <= sum) 
            {
                sum += nums[index];
                index++;
            }
            if (sum < n) {
                if (index < nums.length && nums[index] == sum + 1) 
                    index++;
                else {
                    ans++;
                }
                sum ＝ 2 ＊ sum + 1;
            }
        }
        return ans;
    }