Java solution using greedy approach


  • 0
    C

    Coding solution to https://discuss.leetcode.com/topic/54409/every-big-thing-has-a-small-beginning

       //idea is 1, 2 can make atmost 3
        //        1,2,3 can make atmost 6
        // so for 1,2,3 to make 7, patch should be 4 which will extend the range till 8
        public int minPatches(int[] nums, int n) {
            int patch = 0, idx = 0;
            long numberCanBeReached = 1;
            while(numberCanBeReached <= n){
                if(idx < nums.length){
                    int nextExist = nums[idx];
                    
                    // represents existing number which can potientally contribute later
                    if(nextExist > numberCanBeReached){
                        patch++;
                        numberCanBeReached += numberCanBeReached;
                    }
                    
                    // add the existing number to the range which can be reached.
                    else{
                        numberCanBeReached += nextExist;
                        idx++;
                    }
                }
                
                // if all the exiting numbers are consumed keep increasing the range to its maximum reach
                else{
                    numberCanBeReached += numberCanBeReached;
                    patch++;
                }
            }
            
            return patch;
        }
    

Log in to reply
 

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