class Solution {
public:
int minPatches(vector<int>& nums, int n) {
int ret=0,i=0;
long k=1;
while(k<=n){
if(i==nums.size()nums[i]>k){ret++;k*=2;}
else k+=nums[i++];
}
return ret;
}
};
C++ AC solution

I believe I understand this, this is really cool.
The key idea is that, if range [1k) is covered right now, adding k will double the range, or adding m will extend the range by m.long k=1; // hope to cover "1" while(k<=n){ if(i==nums.size()nums[i]>k){ret++;k*=2;} // if all nums[] are used up, or if the current nums[i] is too large to cover the current desired range, we add k to [1,k) to double the range. else k+=nums[i++]; // if nums[i] is less than k, than the range is only extended by nums[i] } return ret;