✅LeetCode Hard in 6 mins 💯Beats 100% - Explained with [ Video ] - C++/Java/Python/JS - Arrays
\n\n\n\n# YouTube Video Explanation:\n\n **If you want a video for this question please write in the comments** \n\n https://www.youtube.com/watch?v=ujU-jeO1v-k
![Screenshot 2024-06-16 101219.png](https://assets.leetcode.com/users/images/ff67e801-bf2d-4892-994a-a403c2e01141_1718513489.2109172.png)\n\n\n\n# YouTube Video Explanation:\n\n<!-- **If you want a video for this question please write in the comments** -->\n\n<!-- https://www.youtube.com/watch?v=ujU-jeO1v-k -->\n\nhttps://youtu.be/igi901q2uv8\n\n**\uD83D\uDD25 Please like, share, and subscribe to support our channel\'s mission of making complex concepts easy to understand.**\n\nSubscribe Link: https://www.youtube.com/@leetlogics/?sub_confirmation=1\n\n*Subscribe Goal: 2000 Subscribers*\n*Current Subscribers: 1976*\n\n---\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem requires ensuring that any number in the range `[1, n]` can be formed by the sum of some elements in the given sorted array `nums`. The key is to identify the smallest number that cannot be formed (`missing`). If `missing` is in the array, we include it and check the next `missing`. If `missing` is not in the array, we need to add it (patch it) to cover that gap and update our `missing` value accordingly. The goal is to minimize the number of patches required.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize `missing` to 1, which is the smallest number we want to be able to form.\n2. Use a variable `i` to iterate through the array and another variable `patches` to count the number of patches needed.\n3. While `missing` is less than or equal to `n`:\n   - If the current array element (`nums[i]`) is less than or equal to `missing`, add this element to `missing` and move to the next element (`i++`).\n   - If the current array element is greater than `missing`, patch the `missing` value by adding `missing` itself, and increment the `patches` counter.\n4. Repeat until `missing` exceeds `n`.\n5. Return the number of patches needed.\n\n# Complexity\n- Time complexity:  `O(m)`, where `m` is the length of the array `nums`. The while loop iterates through the array at most once, and each patching operation is constant time.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(1)`, as we only use a few extra variables.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n\n\n\n### Explanation with Tables\nLet\'s illustrate the example with `nums = [1, 3]` and `n = 6`.\n\n| Step | Missing Value (`missing`) | Array Element (`nums[index]`) | Action                | Updated Missing Value (`missing`) | Patches |\n|------|----------------------------|-------------------------------|-----------------------|-----------------------------------|---------|\n| 1    | 1                          | 1                             | Add array element     | 2                                 | 0       |\n| 2    | 2                          | 3                             | Patch (add 2)         | 4                                 | 1       |\n| 3    | 4                          | 3                             | Add array element     | 7                                 | 1       |\n\n**Detailed Explanation**:\n1. **Step 1**:\n   - Initial `missing` is 1.\n   - The first element in `nums` is 1, which is less than or equal to `missing`.\n   - Add `nums[i]` to `missing`: `missing` becomes 2.\n   - Move to the next element in `nums`.\n\n2. **Step 2**:\n   - Current `missing` is 2.\n   - The next element in `nums` is 3, which is greater than `missing`.\n   - Patch the `missing` value by adding `missing` itself: `missing` becomes 4.\n   - Increment the `patches` counter to 1.\n\n3. **Step 3**:\n   - Current `missing` is 4.\n   - The next element in `nums` is 3, which is less than `missing`.\n   - Add `nums[i]` to `missing`: `missing` becomes 7.\n   - Since `missing` (7) is now greater than `n` (6), we stop.\n\nAfter these steps, the range `[1, 6]` can be formed using the numbers in `nums` and the patches.\n\n### Summary\n- **Initial `missing`**: 1\n- **Patch if `missing` is not covered**.\n- **Update `missing`** and **count patches** until `missing` exceeds `n`.\n\n\nAfter these steps, all numbers in the range `[1, 6]` can be formed.\n\nFor `nums = [1, 5, 10]` and `n = 20`:\n\n| Step | Missing Value (`missing`) | Array Element (`nums[index]`) | Action                | Updated Missing Value (`missing`) | Patches |\n|------|----------------------------|-------------------------------|-----------------------|-----------------------------------|---------|\n| 1    | 1                          | 1                             | Add array element     | 2                                 | 0       |\n| 2    | 2                          | 5                             | Patch (add 2)         | 4                                 | 1       |\n| 3    | 4                          | 5                             | Patch (add 4)         | 8                                 | 2       |\n| 4    | 8                          | 5                             | Add array element     | 13                                | 2       |\n| 5    | 13                         | 10                            | Add array element     | 23                                | 2       |\n\n\nThus, 2 patches are needed to cover the range `[1, 20]`.\n\n\n# Code\n```java []\nclass Solution {\n    public int minPatches(int[] nums, int n) {\n        long missing = 1;\n        int patches = 0;\n        int index = 0;\n\n        while (missing <= n) {\n            if (index < nums.length && nums[index] <= missing) {\n                missing += nums[index];\n                index++;\n            } else {\n                missing += missing;\n                patches++;\n            }\n        }\n\n        return patches;\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        long missing = 1;\n        int patches = 0;\n        int index = 0;\n\n        while (missing <= n) {\n            if (index < nums.size() && nums[index] <= missing) {\n                missing += nums[index];\n                index++;\n            } else {\n                missing += missing;\n                patches++;\n            }\n        }\n\n        return patches;\n    }\n};\n```\n```Python []\nclass Solution(object):\n    def minPatches(self, nums, n):\n        missing = 1\n        patches = 0\n        index = 0\n\n        while missing <= n:\n            if index < len(nums) and nums[index] <= missing:\n                missing += nums[index]\n                index += 1\n            else:\n                missing += missing\n                patches += 1\n\n        return patches\n\n        \n```\n```JavaScript []\nvar minPatches = function(nums, n) {\n    let missing = 1;\n    let patches = 0;\n    let index = 0;\n\n    while (missing <= n) {\n        if (index < nums.length && nums[index] <= missing) {\n            missing += nums[index];\n            index++;\n        } else {\n            missing += missing;\n            patches++;\n        }\n    }\n\n    return patches;\n};\n```\n\n![upvote.png](https://assets.leetcode.com/users/images/cfa5c8a9-8869-47d8-9404-08ce2f3f9ac1_1718513326.4787874.png)\n
['Array', 'Binary Search', 'Greedy', 'Python', 'C++', 'Java', 'JavaScript']