My 8 ms O(N) C++ code
The basic idea is to use "bound" to save the maximum number that can be generated with nums[0..i-1] and the added numbers (i.e. using nums[0..i-1] and the added
The basic idea is to use "bound" to save the maximum number that can be generated with nums[0..i-1] and the added numbers (i.e. using nums[0..i-1] and the added numbers, we can generate all the numbers in [1..bound]). If bound is less than n and nums[i] is larger than bound+1, then we need to add bound+1, which extend the maximum number that can be generated to bound*2 +1. If nums[i] is no larger than bound+1, then by add nums[i], we can extend the maximum number that can be generated to bound + nums[i].\n\n    class Solution {\n    public:\n        int minPatches(vector<int>& nums, int n) {\n            int len = nums.size(),  i=0, res=0;\n            long long bound = 0;\n            while(bound<n) \n            {// if it does not reach to the end\n                if(i<len && nums[i]<=(bound+1)) bound+=nums[i++]; // if nums[i] is no larger than bound, then including nums[i] allow us to generate all the numbers [1.. bound+nums[i]]\n                else{++res; bound= 2*bound+1;}  // we need to add a new number bound+1, and that extend the bound to 2*bound+1\n            }\n            return res;\n        }\n    };
[]