My 1ms Java Solution


  • 0
    F

    This is a solution that I came up with by myself. If this follows the same idea as yours, there's nothing to be surprised with, as the basic idea for the optimal solution should be unique in most leetcode problems. I tried out several special cases to finally get the high-level idea, and then this solution.

    nextToMaxSum: The next integer to the maximum value of the range that can all be covered up to now. In other words, with some added integers and the elements in array 'nums' we've already checked, nextToMaxSum stands for the first value we cannot reach.

    For example, for nums=[1,1,2,9] and n=23. If we've checked 1,1,2, then 5 is the next integer to the current sum.

    Needless to say, we'll have to add nextToMaxSum to the array, if it's not there yet. For example, we need to add 5 to the array in the example above. However, if nextToMaxSum is already in the array(If nums=[1,1,2,5]), then we don't need to add it.

    Once nextToMaxSum is added to the array, the range almost doubles: Previously, it's (nextToMaxSum-1), but now, it's (nextToMaxSum-1+nextToMaxSum=2nextToMaxSum-1). So the new value for nextToMaxSum should be 2nextToMaxSum. Similarly, if we have an element x in array 'nums', then now the bound should be x+nextToMaxSum-1.

    public class Solution {
        public int minPatches(int[] nums, int n) {
            int cnt;
            int patches = 0;
            long nextToMaxSum = 1;
            
            for(cnt = 0; cnt<nums.length && nextToMaxSum-1<n; ){
                if(nextToMaxSum < nums[ cnt ]){ 
                    nextToMaxSum = nextToMaxSum << 1;
                    patches++;
                } else {
                    nextToMaxSum += nums[ cnt++ ];
                }
            }
            
            while(nextToMaxSum-1 < n){
                nextToMaxSum = nextToMaxSum << 1;
                patches++;
            }
            
            return patches;
        }
    }
    

    As for the time complexity, since we need to iterate through array 'nums', it's at least O(nums.length). Also, we need to keep doubling nextToMaxSum from 1, until it exceeds n. Since n is an integer that has only 32 bits, the time complexity for this is a constant. So the total time complexity is O(nums.length+32)=O(nums.length)


  • 0
    C

    thats genius!


Log in to reply
 

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