Python solution + clear explanation, o(|nums| + log n)
We want to form all numbers from 1 to n. Let's assume we already have the solutions for a smaller problem. We have an array to reach all numbers up to k, 1 <= k
We want to form all numbers from 1 to n. Let's assume we already have the solutions for a smaller problem. We have an array to reach all numbers up to k, 1 <= k < n, but not more. We have used nums<sub>0</sub> to nums<sub>i</sub> to create that array plus some patches. The next element is k+1. There is no way we can create k+1 with our current array (we defined the array that way), so I need to add a new element to it, nums<sub>i+1</sub>. As my previous array was able to give all elements from 1 to k, adding nums<sub>i+1</sub> will give me all elements between 1 and k+nums<sub>i+1</sub>.\n\nThe trick here is to find those compact arrays that are able to produce all values between 1 and k. We can do that starting in k=1 and adding elements from nums or patching our array. To reach k=1 I need a 1. If nums_0 is 1, I can add it to my array otherwise I need to pad with 1. To reach k=2 I need another 1 or a 2.\n\nAnd so on. So, if you keep track of the highest number you can reach in your current array there could be two possibilities:\n- nums<sub>i</sub> is smaller than k. Just increase k.\n- nums<sub>i</sub> is bigger than k. That means that you can't create any number between k+1 and nums<sub>i</sub>-1. Add k+1 instead. That will move k to 2*k+1.\n\nRepeat until k>=n.\n\n```python\ndef minPatches(self, nums, n):\n    i, k, added = 0,0,0\n    while k < n:\n        if i < len(nums) and nums[i] <= k+1:\n            k += nums[i]\n            i+=1\n        else:\n            k += k+1\n            added += 1\n    return added\n```
[]