The basic idea is very simple. We search from 0 in ascending order. And greedily add a new number if there's a hole----If you know what I mean.
_sum represent the current sum that we can cover. and you can see I only do
ans += 1 when the new coming
nums[index] is bigger than the
_sum, and that's when the hole occur.
Here's my code.
class Solution(object): def minPatches(self, nums, n): """ :type nums: List[int] :type n: int :rtype: int """ _sum, ans, index = 0, 0, 0 while _sum < n: while index < len(nums) and nums[index] <= _sum + 1: _sum += nums[index] index += 1 if _sum < n: ans += 1 _sum = _sum * 2 + 1 return ans # 52ms ,beat 70.48%