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


  • 2

    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)
        not found ,  so add 2 to the nums
    

    miss=4 : i=1

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

    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!
    

    return added=2

    Code:

    class Solution {
    public:
        int minPatches(vector<int>& nums, int n) {
            long miss=1, added=0, i=0;
            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;
                    added++;
                }
            }
            return added;
        }
    };

  • 1

    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;
        }
    };

Log in to reply
 

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