# 1ms Java solution with explain

• ``````public int minPatches(int[] nums, int n) {
int index = 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){
canReachTo = (canReachTo << 1) + 1;
} else {
canReachTo = nextExisting + canReachTo;
index++;
}
} else {
canReachTo = (canReachTo << 1) + 1;
}
}
}
``````

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.

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

• You can combine the 4 branches into two.

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

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