###### tags: `LeetCode` `Hard`
# LeetCode #330 [Patching Array](https://leetcode.com/problems/patching-array/)
### (Hard)
給定一個已排序的正整數數組 nums，和一個正整數 n 。從 [1, n] 區間內選取任意個數字補充到 nums 中，使得 [1, n] 區間內的任何數字都可以用 nums 中某幾個數字的和來表示。請輸出滿足上述要求的最少需要補充的數字個數。

---
設定一maxvalue代表目前能到達的最大值, 初始值為0, 型態為long long。

令count為0負責計算需要增加的數字數量, 另i為0計算現在讀取到的nums位置。

當maxvalue+1小於下一個nums[i]並且nums[i]還不到nums的尾端時, 這時候需要新增一個數為maxvalue+1, 更新最大值為2*maxvalue+1(也就是原本的maxvalue加上maxvalue+1); 而若maxvalue+1大於等於nums[i], 則更新maxvalue為maxvalue+nums[i]。

舉例: nums = [1,2,5,6,20], n(target)=50

一開始maxvalue為0, i=0, count=0。

i=0 : 0+1≥nums[0] (1), 更新maxvalue=1, i++
i=1 : 1+1≥nums[1] (2), 更新maxvalue=1+2=3, i++
i=2 : 3+1<nums[2] (5), 代表此時需要新增4來補足array的連續性, count=1, maxvalue=3+4=7

(要注意由於已經達成4之前的數的連續性也就是1,2,3皆存在, 這代表搭配上4時, 5,6,7皆存在, 也就是說7之前的連續性皆已滿足)

i=2 : 7+1≥nums[2] (5), 更新maxvalue=7+5=12, i++
i=3 : 12+1≥nums[3] (6), 更新maxvalue=12+6=18, i++
i=4, 18+1<nums[4] (20), 此時須補足19, 因此maxvalue+=maxvalue+1=37, count=2
i=4, 37+1≥nums[4] (20), 更新maxvalue=37+20=57(超過目標50, 迴圈中止)

答案count為2, 新增的數為[4,19]

---

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        long long maxx=0;
        int count=0;
        int i=0;
        
        while(maxx<n){
            if(i<nums.size()&&nums[i]<=maxx+1){
                maxx+=nums[i];
                i++;
            }
            else{
                maxx+=(maxx+1);
                count++;
            }
        }
        return count;
    }
};