O(n) if given array are sorted, 1 ms, Java, with comment


  • 0
    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;
        }
    }
    

Log in to reply
 

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