```
public class Solution {
public int minPatches(int[] nums, int n) {
/**
* Idea : e.g. 1,3,5 10 ==> 1,(2),3,4,5,6,(7),8,9,(10)
* e.g. 1,3 8 ==> 1,(2),3,4,(5),(6),((7)),(8)
* double parentheses means the second missing number
* always update the range using the smallest unused num in the array
* if num > currentRange + 1, we need to add "currentRange" as the missing num, and update range to range*2 - 1
* else, range = range + num
*/
if (n <= 0) {
return 0;
}
long num = (long) n;
long pointer = 1;
int index = 0;
int numNeeded = 0;
while (pointer <= num) {
if (index >= nums.length || pointer < nums[index]) {
numNeeded ++;
pointer += pointer;
} else {
pointer += nums[index++];
}
}
return numNeeded;
}
}
```