Easy to Understand 1ms Java solution


  • 2
    T
    public int minPatches(int[] nums, int n) {
        if(n<1) return 0;
        int patch=0;//number of patches
        int covers=0;//the cover range of current array
        for(int i=0;i<nums.length;i++){
            if(covers>=n) return patch;
            while(nums[i]-covers>1){
                patch++;  //patch the covers+1
                covers=covers*2+1;
                if(covers>=n) return patch;
            }
            if(nums[i]>Integer.MAX_VALUE-covers) return patch;
            covers=nums[i]+covers;
        }
        while(covers<n){
            patch++;
            if(covers>Integer.MAX_VALUE-covers) return patch;
            covers=covers*2+1;
        }
        return patch;
    }

  • 0
    H

    Maybe it is better to do in this way:

    public int minPatches(int[] nums, int n) {
            if(n<1) return 0;
            int patch=0;//number of patches
            long covers=0;//the cover range of current array
            for(int i=0;i<nums.length;i++){
                if(covers>=n) return patch;
                while(nums[i]-covers>1){
                    patch++;  //patch the covers+1
                    covers=covers*2+1;
                    if(covers>=n) return patch;
                }
                covers=nums[i]+covers;
            }
            while(covers<n){
                patch++;
                covers=covers*2+1;
            }
            return patch;
        }
    

    I changed the type of covers from int to long. So no longer need if(covers>Integer.MAX_VALUE-covers) return patch;


Log in to reply
 

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