Simple 9-line Python Solution


  • 9
    M
    class Solution(object):
        def minPatches(self, nums, n):
            """
            :type nums: List[int]
            :type n: int
            :rtype: int
            """
            miss, i, added = 1, 0, 0
            while miss <= n:
                if i < len(nums) and nums[i] <= miss:
                    miss += nums[i]
                    i += 1
                else:
                    miss += miss
                    added += 1
            return added

  • 0
    W

    @myliu

    Your solution is awesome. But your idea will be more clear if given some explanation. The miss means all numbers from 1 ~ miss - 1 is covered (the while condition "miss <= n" instead of "miss < n" proved it).

    An important fact is that "every number can be presented as binary". For example, 21 = 1* 2^4 + 0 * 2^3 + 1 * 2^2 + 0 * 2^1 + 1 * 2^0. That explains why you did "miss += miss" when miss < num[i]. Every time you add a miss += miss, it actually makes sure that every number from 1 to miss-1 (miss is the updated miss) is covered. And every time when miss >= nums[i], We can reach all new numbers from miss ~ miss + num[i] - 1 simply by add the nums[i] to (1 ~ miss - 1).


Log in to reply
 

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