330. Patching Array

I just follow the top voted solution. The idea is brilliant. The key is that assuming array [a1, a2, a3] can build [1,...,sum], where sum = a1+a2+a3, then for a new coming number a4, if a4 is less than or equal to sum, we definitely can build [1,...,sum+a4]. Otherwise, we need to patch a number and the right number patch is sum+1 such that the interval can be doubled. The reason is if you patch a number larger than sum, then you can’t cover (sum, p), and on the other hand, if you patch a number less than sum, your new covered interval is shorter than [1,...,2sum].

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