# [recommend for beginners]clean C++ implementation with detailed explanation

• we run the code on an example to illustrate the ideas:

``````    [1, miss)   : the right miss is open field

nums=[1,5,10]      n=20

initialize state : miss=1   i=0   size=3
``````

miss=1 : i=0

``````    if find [number<=1] in nums {  i++  }  else add 1 to nums   update    miss+=1         [1,2)
found 1,  i++, so added 1 to the nums
``````

miss=2 : i=1

``````    if find [number<=2] in nums  { i++ }   else add 2 to nums    update  miss+=2;        [1,4)
``````

miss=4 : i=1

``````    if find [number<=4] in nums  { i++ }   else add 4 to nums    update  miss+=2;        [1,8)
``````

miss=8: i=1

``````    if find [number<=8] in nums  { i++ }   else add 8 to nums    update  miss+=2;        [1,13)
found 5 , so add 5 to the nums
``````

miss=13:i=2

``````    if find [number<=13] in nums  { i++ }   else add 13 to nums    update  miss+=2;        [1,23)
found 10 , so add 10 to the nums
``````

miss=23

``````    covers [1,20], done!
``````

Code:

``````class Solution {
public:
int minPatches(vector<int>& nums, int n) {
while(miss<=n){
/*** update the miss to the (miss+nums[i]) **/
if(i<nums.size() && nums[i]<=miss){
miss+=nums[i++];
}else{
/*** update the miss to the miss+miss **/
miss+=miss;
}
}
}
};``````

• This solution is a little bit tricky , we just loop from miss=1 and check whether 1 .... exist or not ?

Then we update the miss to bigger field in the procedure of the loopping over all the vector !

Here is the final AC implementation ....

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.