# Share my explanation and code

• Assume the upper bound we can not reach is miss, i.e the largest number we can reach is (miss-1), i.e we can already reach number among [1, miss-1] (both inclusive), what number should we patch to reach miss?
We can patch any number among [1, miss] (both inclusive), but only patching the largest number can make sure we patch least count of numbers, because the by patching the largest number, we extend to the largest upper bound.
For example currently the upper bound is miss, so we can already reach [1, miss-1], the after patching miss, the largest number we can reach is miss-1+miss, so then upper bound becomes miss + miss;

``````public class Solution {
public int minPatches(int[] nums, int n) {
int i = 0; //beginning index
long miss = 1; //current upper bound
int count = 0; //count of number patched

while(miss <= n){
if(i == nums.length || (i < nums.length && nums[i] > miss)){
//i == nums.length means there's no given number, so we can only patch a number
//we want to reach nums[i], but currently we only reach miss-1
//so we should patch miss to extend to the largest upper bound
//after patching, we can reach miss-1+miss
//so the upper bound should be miss += miss
miss += miss;
count++;
}
else if(i < nums.length && nums[i] <= miss){
//we want to reach nums[i], but we already reach miss-1
//so we can actually reach nums[i]+miss-1
//so the upper bound should be nums[i]+miss
miss += nums[i];
i++;
}
}
return count;
}
}
``````

The code is not very concise, but the redundancy makes the code easier to understand.

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