1ms Java solution with explain


  • 8
    C
    public int minPatches(int[] nums, int n) {
        int index = 0;
        int addedCount = 0;
        long canReachTo = 0;
        while( canReachTo < n){
            if( nums.length > index){
                int nextExisting = nums[index];
                if(nextExisting == canReachTo + 1){
                    canReachTo = (canReachTo << 1) + 1;
                    index++;
                } else if(nextExisting > canReachTo + 1){
                    addedCount++;
                    canReachTo = (canReachTo << 1) + 1;
                } else {
                    canReachTo = nextExisting + canReachTo;
                    index++;
                }
            } else {
                addedCount++;
                canReachTo = (canReachTo << 1) + 1;
            }
        }
        return addedCount;
    }
    

    This solution is based on greedy method.
    For example, if you have 1, 2, it can reach 2+(2-1) = 3. So when we want to add up to 4, we have to add 4 into the list. And 1,2,4 can reach to 4+(4-1).
    Similarly, for any added number n, they can add up to n+(n-1) without missing one number.
    If there is one number x which satisfies n < x < n+(n-1), then we don't have to worry about the numbers until x + n + n - 1. Repeatedly evaluate the next number that the list of numbers can reach to, and add into the list next one when missing.
    So basically this method is <log(n) time complexity and O(1) space complexity.


  • 0
    J

    Why if you have 1, 2, it can reach 2+(2-1) = 3.
    Could you elaborate?


  • 0
    H

    You can combine the 4 branches into two.


  • 0
    C

    is there any difference between X<<1 and X*2?


  • 0
    C

    @callumhu
    With C++, it <<1 is faster than *2. However, if you are using java, *2 is in fact performing better.


  • 0
    C

    @jadetang
    if you can reach 1,2,...n-1,n, then you are able to reach n+1, n+2, n+3....n+n-1
    so that in 2+(2-1), n=2;


Log in to reply
 

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