C++ 4ms 98% greedy solution w/ explanation
The idea is to greedily add the maximum missing number, and the numbers from nums once we can reach those numbers.\n\nWhy this works\n\nAssume we have nums = [1
The idea is to greedily add the maximum missing number, and the numbers from ```nums``` once we can reach those numbers.\n\n**Why this works**\n\nAssume we have ```nums = [1, 5, 10]``` and we want all numbers to 20. To start thing off, we need to look for a 1. We have a 1 in the array, so are we good. Then we look for a 2. We do not have a 2 in the array, and the next element in the array is 5. This means **we must add a patch to get ```2```**. \n\nHow do we decide which patch to add? Well since we already have `1`, we can either add a `1`, or we can add a `2`. However, if we add a `2`, we will be able to make ```2``` _and_ ```3```, but if we add a ```1```, we will only be able to get ```2```. Since we want the minimum number of patches, we should aim to maximize the new numbers we can make from each patch. \n\nNow we can make ```[1, 4)```, and we are missing `4`, so by the previous logic we would add a `4` as the second patch, to get all numbers between ```0``` and ```7```. If we look at the next number in `nums`, we can see that it is a 5, so we have already covered it. But this is a "free" number. We can add it to any of our sums from ```0 ... 7``` and get a new number. The maximum number is now ```12```. This means we are able to increase the numbers we can reach _without having to add a patch_. Thus, we keep this up, and either add mandatory patches that maximizes the numbers we get, or add in free numbers from ```nums``` that extends our maximum range, until we reach the required range.\n\n```\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        uint32_t m = 1, i = 0, p = 0, size = nums.size();\n        while(m <= n) {\n            if(i < size && nums[i] <= m) m += nums[i++];\n            else {\n                m += m;\n                ++p;\n            }\n        }\n        return p;\n    }\n};\n\nauto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();\n```
[]