Why not you tried Prefix Sum !!! Greedy Approach O(logN)
Intuition\nIf we have non-descending array [a, ....., b, c, ....., d] and the consecutive numbers formed from subarray [a, ....., b] are k and c >= k-1,  then w
# Intuition\nIf we have non-descending array $$[a, ....., b, c, ....., d]$$ and the consecutive numbers formed from subarray $$[a, ....., b]$$ are $$k$$ and $$c >= k-1$$,  then we can ensure that the consecutive numbers formed from subarray $$[a, ....., b, c]$$ will be $$k+c$$.\n\nFor example,\nGiven $$nums = [1,2,3,6,13]$$ and for subarray $$[1,2,3]$$ we know that we can form all the numbers from *1 to 6* *({1, 2, 3, 3+1=4, 3+2=5, 3+2+1=6})*. \nNow next number in subarray is 6, which follows the condition $$c >= k-1$$ i.e., $$(6 >= 6 - 1)$$. So, now we can say that the consecutive numbers formed from subarray $$[1,2,3,6]$$ will be $$6 + 6 = 12$$.\nWe can visualize it as, if we can form all the numbers taking numbers from the previous subarray, here then adding 6 to all that numbers, we can get all the other 6 for next subarray.\nviz., \nfor subarray $$[1,2,3]$$ we get all the numbers from *1 to 6* *({1, 2, 3, 3+1=4, 3+2=5, 3+2+1=6})*, then after adding 6 to each number we can get other numbers from *6 to 12* *({6, 1+6=7, 2+6=8, 3+6=9, 1+3+6=10, 2+3+6=11, 1+2+3+6=12})*.\n\nAgain, for the next index which satisfies the condition, numbers formed will be $$12+13=25$$.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIn the loop, for each index, if the condition gets true, we add it to prefix sum and move to next index. If the condition doesn\'t satisfy, it infers that some of the numbers are missing, that we need to add, so we increases the missing numbers value (answer) and also add up the largest number which will cover all the in between values, i.e. `prefix sum + 1`, to the `prefix sum`.\n\nIn case, if we our numbers form doesn\'t reach to the `n`, we will loop it until we reach there.\n\n# Complexity\n- Time complexity: max(O(len(nums)), O(log n)) = **O(logN)**\n\n- Space complexity: **O(1)**\n\n# Code\n\n### C++ :\n```\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        int ans = 0;\n        long int presum = 0;\n        for(int i=0; i<nums.size() and presum < n;) {\n            if(presum >= nums[i]-1) {presum += nums[i]; i++;}\n            else {ans += 1; presum += presum+1;}\n        }\n        while(presum < n) {presum += presum+1; ans += 1;}\n        return ans;\n    }\n};\n\n```\n\n### Python3 :\n```\nclass Solution:\n    def minPatches(nums, n):\n        prefix_sum, res, i = 0, 0, 0\n        while i < len(nums) and prefix_sum < n:\n            if prefix_sum >= nums[i] - 1:\n                prefix_sum += nums[i]\n                i += 1\n            else:\n                prefix_sum += prefix_sum + 1\n                res += 1\n        while prefix_sum < n:\n                prefix_sum += prefix_sum + 1\n                res += 1\n        return res\n```\n# .\n## .\n### .\n# >>>>>>>>>>**Please Upvote**<<<<<<<<<<<\n### .\n## .\n# .
['Array', 'Greedy', 'C', 'Sorting', 'Prefix Sum', 'C++', 'Python3']