✅5 lines only , Fastest Greedy Efficient Simplest Solution with DryRun in C++
Intuition\n Describe your first thoughts on how to solve this problem. \n> First of all, we have to understand what we want.\n\nWe want that nums must have the 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n> First of all, we have to understand what we want.\n\nWe want that `nums` must have the required elements, so that there combinations of numbers will sum upto n, i.e., from `[1,n]` both inclusive.\n**At every step we will check , for each `nums[i]`, Is it possible to make all numbers from `[1, (nums[i]+ nums[i+1]....nums[j]) ]` where `0 <= i < nums.size()` and where `i+1 <= j < nums.size()` by combining different combinations of numbers present in nums.**\n*Inside this :-*\n***If yes :- \nIt means we have all the numbers from `[1,nums[i] + nums[i+1] + ... nums[j]]`***\n\n***If No :-\nIt means we have to add some elements so that so that it can generate all elements from `[1,nums[i] + nums[i+1] + ... nums[j] + k]` where k > 0.***\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nInitially, we want that the nums must produce 1 as the minimum sum.\n- Initialise variables :-\n```\nlong nextRequiredMinimumSum = 1; // It means what is the total sum value required to get all numbers from 1 to nextRequiredMinimumSum.\nint patchedElements = 0; // number of added elements in the nums.\nint i = 0; // for iterating the nums vector\n```\n- Start a while loop with condition as, while the nextRequiredMinimumSum is less than equal to n :- \n```\nwhile(nextRequiredMinimumSum <= n) {\n}\n```\n- If the `nextRequiredMinimumSum` is greater than or equal to the current value of `nums[i]`, it means we can generate all numbers from `[1 , nextRequiredMinimumSum]`. It means now we can generate numbers from `[1 , nextRequiredMinimumSum + nums[i]]`. We can iterate to the next number. i.e., `i++`.\n```\n// \nif(i < nums.size() && nextRequiredMinimumSum >= nums[i]) {\n    nextRequiredMinimumSum += nums[i];\n    i++;\n}\n```\n- Else, this means, we can\'t generate the numbers from `[1 , nextRequiredMinimumSum]`. But we are sure , that we can generate all numbers from `[1 , nextRequiredMinimumSum - 1]`, because in the else case, we are always adding the nextRequiredMinimumSum.\n```\nelse {\n    nextRequiredMinimumSum += nextRequiredMinimumSum;\n    patchedElements++;\n}\n\n```\n---\nlet me give you an example :-\n**- DRY RUN :-**\nlet nums = {1,2,9,10}, n = 20\n\nWhen i = 0, \n`i = 0`, `nums[i] = 1`, `nextRequiredMinimumSum = 1`, \n**nextRequiredMinimumSum >= nums[i]** , (1 >= 1)\ntherefore, **nextRequiredMinimumSum = 1 + 1 = 2** , **i++.**\n\n---\n\nWhen i = 1, `i = 1`, `nums[i] = 2`, `nextRequiredMinimumSum = 2`, **nextRequiredMinimumSum >= nums[i]** , (2 >= 2)\ntherefore, **nextRequiredMinimumSum = 2 + 2 = 4**, **i++.**\n\n---\n\nWhen i = 2, `i = 2`, `nums[i] = 9`, `nextRequiredMinimumSum = 4`, **nextRequiredMinimumSum < nums[i]** , (4 < 9) , **patchedElements++.**\n\n> but, you can see , previously we were able to generate till 3. i.e., till nextRequiredMinimumSum - 1.\n\n**nextRequiredMinimumSum += 4**, therefore, **nextRequiredMinimumSum = 8**.\n\n---\n\nNow, **nextRequiredMinimumSum <= n** therefore, check again , `i = 2`, `nums[i] = 9`, `nextRequiredMinimumSum = 8`,  **nextRequiredMinimumSum < nums[i]** , (8 < 9) , **patchedElements++.**\n> but, you can see , previously we were able to generate till 7. i.e., till nextRequiredMinimumSum - 1;\n\n**nextRequiredMinimumSum += 8**, therefore, **nextRequiredMinimumSum = 16**.\nIt means we are able to make till 15, i.e., nextRequiredMinimumSum - 1.\n\n---\n\nNow, **nextRequiredMinimumSum <= n** therefore, check again , `i = 2`, `nums[i] = 9`, `nextRequiredMinimumSum = 16`,  **nextRequiredMinimumSum >= nums[i]** , (16 >= 9)\ntherefore, **nextRequiredMinimumSum = 16 + 9 = 25** , **i++.**\n\n---\n\nNow, **nextRequiredMinimumSum > n** , (25 > 20), therefore, break the while loop. \n\n**return the patchedElement**s.\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```C++ []\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        long nextRequiredMinimumSumPossible = 1; int patchedElements = 0, i = 0, size = nums.size();\n        while(nextRequiredMinimumSumPossible <= n)\n            if(i < size && nextRequiredMinimumSumPossible >= nums[i]) nextRequiredMinimumSumPossible += nums[i] , i++;\n            else nextRequiredMinimumSumPossible += nextRequiredMinimumSumPossible, patchedElements++;\n        return patchedElements;\n    }\n};\n```\n\n![upvote.jpeg](https://assets.leetcode.com/users/images/ce196c66-2e6f-4dec-8e30-c25c2f1f7fd3_1706881698.9688694.jpeg)\n![upvote.jpeg](https://assets.leetcode.com/users/images/ce196c66-2e6f-4dec-8e30-c25c2f1f7fd3_1706881698.9688694.jpeg)\n\n\n[Instagram](https://www.instagram.com/iamsidharthaa__/)\n[LinkedIn](https://www.linkedin.com/in/sidharth-jain-36b542133)\n**If you find this solution helpful, consider giving it an upvote! Your support is appreciated. Keep coding, stay healthy, and may your programming endeavors be both rewarding and enjoyable!**
['Array', 'Greedy', 'Sorting', 'C++']