Python O(n) with detailed explanation
Initialize an empty list, keep adding new numbers from provided nums into this list, keep updating the coverage range and ensure a continus coverage range. If y
Initialize an empty list, keep adding new numbers from provided nums into this list, keep updating the coverage range and ensure a continus coverage range. If you do so, you only need to care about whether the newly added number will break the coverage range or not.\n\nSuppose 1~10 is already covered during this process, (by whatever combinations in the above list, doesn\'t matter), then for the next number added\n1. If the next number is "11", you will have these new sums: \n      11, 11+1, 11+2, ..., 11+10, so your total coverage becomes 1~21, which is "2 x coverage + 1"\n2. If the next numberis smaller than "11", for example "3", then the new coverage becomes: 10+3, 9+3, 8+3-> 1~13, which is "num + coverage"\n3. If the next number is bigger than "11", for example "12", then number "11" is missing forever. There is no way to sum 11 by existing combinations. You have to manually patch "11" before being able to process the next number. Note that Patching number "1~10" can also cover the missing "11", but patching "11" is optimal because it maximizes the total coverage.\n\n```\nclass Solution:\n    def minPatches(self, nums: List[int], n: int) -> int:\n        covered=0\n        res=0\n        for num in nums:\n            while num>covered+1:\n                res+=1\n                covered=covered*2+1\n                if covered>=n:\n                    return res\n            covered+=num\n            if covered>=n:\n                return res\n        while covered<n:\n            res+=1\n            covered=covered*2+1            \n        return res\n```\n\nShorter version with same logic:\n```\nclass Solution:\n    def minPatches(self, nums: List[int], n: int) -> int:\n        covered,res,i=0,0,0\n        while covered<n:\n            num=nums[i] if i<len(nums) else math.inf\n            if num>covered+1:\n                covered=covered*2+1\n                res+=1\n            else:\n                covered+=num\n                i+=1       \n        return res\n```
[]