🔥 🔥 🔥 💯 Easy to understand | Greedy Approach | Detailed Explanation 🔥 🔥 🔥
To look into solutions to other problems visit my leetcode profle\n\n# Intuition\n\n- The code works like providing change with limited coin denominations. Supp
To look into solutions to other problems visit my [leetcode profle](https://leetcode.com/u/bhanu_bhakta/)\n\n# Intuition\n\n- The code works like providing change with limited coin denominations. Suppose you need to cover every amount up to \uD835\uDC5B cents. If you can\'t make exact change for a particular amount miss, it indicates you lack a coin of value less than or equal to miss. To fill this gap, you add a coin of that exact missing amount. This addition allows you to now cover new amounts up to 2 * miss. Repeat this process until you can provide change for every amount up to \uD835\uDC5B. This method ensures you add the minimum number of new coins needed to cover any shortages.\n\n# Approach\nIf its hard to understand the approach, I have clear explanation [here](https://www.youtube.com/watch?v=vmKXw3lgt7I).\n\n- **Initialize Variables:** Start with miss set to 1, added to 0, and index i at 0 to track the smallest sum that cannot be formed and the number of patches added.\n\n- **Iterate with Condition:** Continue the loop as long as miss (the target sum we need to achieve) is less than or equal to n.\n\n- **Use Existing Numbers:** Check if the current number in the list (nums[i]) can be used to form miss. If yes, add it to miss to extend the range of formable sums and increment the index i.\n\n- **Add Necessary Numbers:** If nums[i] is greater than miss or all numbers are already used, add miss itself to cover the smallest unformable sum, and double the value of miss.\n\n- **Increment Added Count:** Whenever a number is added to cover a gap, increase the added counter.\n\n- **Return Total Patches:** Once miss exceeds n, return the total count of added numbers as the result, representing the minimum patches needed to form every number up to n.\n\n**Example:**\n\n**Input: [1, 5, 10]**\n\n| Step | Current nums | Miss | Action | Reason                                   | New Coverage |\n|------|--------------|------|--------|------------------------------------------|--------------|\n| 1    | [1, 5, 10]   | 1    | Use 1  | 1 is available and matches miss          | Sums up to 1 |\n| 2    | [1, 5, 10]   | 2    | Add 2  | 5 is too large to form sum 2             | Sums up to 3 |\n| 3    | [1, 5, 10]   | 4    | Add 4  | 5 is too large to form sum 4             | Sums up to 7 |\n| 4    | [1, 5, 10]   | 8    | Use 5  | Can use 5 with existing numbers to form 8| Sums up to 12 |\n| 5    | [1, 5, 10]   | 13   | Use 10 | Can use 10 with existing numbers to form 13 | Sums up to 22 |\n\n# Complexity\n- Time complexity:\n**O(N)**\n\n- Space complexity:\n**O(1)**\n\n# Code\n```Python []\nclass Solution:\n    def minPatches(self, nums: List[int], n: int) -> int:\n        miss = 1\n        result = 0\n        i = 0\n\n        while miss <= n:\n            if i < len(nums) and nums[i] <= miss:\n                miss += nums[i]\n                i += 1\n            else:\n                miss += miss\n                result += 1\n\n        return result\n\n```\n```C++ []\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        long long miss = 1;\n        int result = 0;\n        size_t i = 0;\n\n        while (miss <= n) {\n            if (i < nums.size() && nums[i] <= miss) {\n                miss += nums[i];\n                i++;\n            } else {\n                miss += miss;\n                result++;\n            }\n        }\n\n        return result;\n    }\n};\n```\n```Java []\nclass Solution {\n    public int minPatches(int[] nums, int n) {\n        long miss = 1;\n        int result = 0;\n        int i = 0;\n\n        while (miss <= n) {\n            if (i < nums.length && nums[i] <= miss) {\n                miss += nums[i];\n                i++;\n            } else {\n                miss += miss;\n                result++;\n            }\n        }\n\n        return result;\n    }\n}\n```\n```Go []\nfunc minPatches(nums []int, n int) int {\n\tmiss := int64(1)\n\tresult := 0\n\ti := 0\n\n\tfor miss <= int64(n) {\n\t\tif i < len(nums) && int64(nums[i]) <= miss {\n\t\t\tmiss += int64(nums[i])\n\t\t\ti++\n\t\t} else {\n\t\t\tmiss += miss\n\t\t\tresult++\n\t\t}\n\t}\n\n\treturn result\n}\n```\n```Kotlin []\nclass Solution {\n    fun minPatches(nums: IntArray, n: Int): Int {\n        var miss: Long = 1\n        var result = 0\n        var i = 0\n\n        while (miss <= n) {\n            if (i < nums.size && nums[i].toLong() <= miss) {\n                miss += nums[i]\n                i++\n            } else {\n                miss += miss\n                result++\n            }\n        }\n\n        return result\n    }\n}\n```\n```Javascript []\n/**\n * @param {number[]} nums\n * @param {number} n\n * @return {number}\n */\nvar minPatches = function (nums, n) {\n    let miss = 1; // JavaScript uses let for block scope variables\n    let result = 0;\n    let i = 0;\n\n    while (miss <= n) {\n        if (i < nums.length && nums[i] <= miss) {\n            miss += nums[i];\n            i++;\n        } else {\n            miss += miss;\n            result++;\n        }\n    }\n\n    return result;\n};\n```\n\n**If you like the solution please upvote**\n![upvote.webp](https://assets.leetcode.com/users/images/e40e064e-b2d1-4ccb-bdd7-91647aafd66b_1718498724.101084.webp)\n
['C++', 'Java', 'Go', 'Python3', 'Kotlin', 'JavaScript']