Python, O(n), greedy
Consider some prefix of our array and say the minimal number it can\'t achieve is minn, if the next number is greater than minn we won\'t be able to achieve min
Consider some prefix of our array and say the minimal number it can\'t achieve is `minn`, if the next number is greater than `minn` we won\'t be able to achieve `minn` at all (since all numbers are increasing and greater than `minn`) thus next number must be less or equal than `minn` if not so we need to patch with such a number. Say our next number `k` satisfies being less or equal than `minn` or otherwise we patched it with some number `k`, then in the new prefix minimal number it can\'t achieve will be `minn + k` and so on we keep maintaining our minimal unachievable number until it is greater than `n`. It is better to patch with such `k` that maximizes `minn+k` and satisfies `k<=minn`, such `k` is actually equal to `minn`. (This part is greedy). After performing such linear scan we will achieve what we want.\n\n```\nclass Solution:\n    def minPatches(self, nums, n):\n        i, ct, minn = 0, 0, 1\n        while minn <= n:\n            if i < len(nums) and nums[i] <= minn:\n                minn += nums[i]\n                i += 1\n            else:\n                minn += minn\n                ct += 1\n        return ct\n```
[]