Share my explanation and code

  • 1

    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;

    For more details, please read the comment in the code:

    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;
                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];
            return count;

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

Log in to reply

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