C++ AC solution


  • 1
    H
    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;
        }
    };

  • 0
    V

    need some annotation


  • 0
    J

    I believe I understand this, this is really cool.
    The key idea is that, if range [1-k) 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;
    

Log in to reply
 

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