100% Beats | Easy to Understand | Detailed Step by Step Explaination | Greedy Approach
Problem Statement\nWe are given a sorted integer array nums and an integer n. Our task is to determine the minimum number of patches required to ensure that any
# Problem Statement\nWe are given a sorted integer array `nums` and an integer `n`. Our task is to determine the minimum number of patches required to ensure that any number in the range `[1, n]` can be formed by summing some elements from the array `nums`. Each element in `nums` can only be used once.\n\n# Highly Optimised with 100% beats\n![Solution.png](https://assets.leetcode.com/users/images/99e547c4-6eee-47fc-9da7-0736f1cd471b_1718508554.8704815.png)\n\n\n# Intuition\nWhen I first looked at the problem, I understood that we need to ensure every number from 1 to n can be formed using elements in a sorted array `nums`. My initial thought was to use a greedy strategy because it seemed efficient. \n\n# Approach\n### Step 1: **Start with Initialization**:\n   - Begin with `missing = 1`. This variable represents the smallest number that we cannot yet form using the elements from `nums`.\n   - Also, set `patches = 0` to keep track of how many patches we need to add.\n\n### Step 2: **Traverse through `nums`**:\n   - Iterate through the sorted array `nums`.\n   - For each number `num` in `nums`, check if it can help in forming the current range up to `missing`.\n\n### Step 3: **Handling the Current Number**:\n   - If `num` is less than or equal to `missing`, it means we can extend our coverage using `num`.\n     - Update `missing` to `missing + num` to reflect that we can now form sums up to this new value.\n   - If `num` is greater than `missing`, there\'s a gap between `missing` and `num - 1` that needs to be covered.\n     - To cover this gap, add `missing` to `nums` and increment `patches`.\n     - Update `missing` to `missing + missing` because now we can form sums up to `2 * missing`.\n\n### Step 4: **Repeat Until Coverage**:\n   - Continue the above steps until `missing` exceeds `n`. This ensures that every number from 1 to n can be formed using elements from `nums` and the patches added.\n\n### Step 5: **Count and Return**:\n   - After exiting the loop, `patches` will contain the minimum number of patches required.\n\n### Example\nLet\'s go through an example with `nums = [1, 3]` and `n = 6`:\n\n- **Initialization**: Start with `missing = 1`, `patches = 0`.\n  \n- **Step 1**: \n  - `num = 1`: `1 <= missing`, so update `missing = 2`.\n  \n- **Step 2**:\n  - `num = 3`: `3 > missing`, so add `missing = 2` to `nums` and increment `patches`. Now `missing = 4`.\n  \n- **Step 3**:\n  - Continue the loop until `missing > n`, ensuring all numbers up to `n` can be formed.\n\n# Complexity\n- **Time Complexity**: ``O(m + log n)``\n  \n- **Space Complexity**: ``O(1)``\n\n# Code\nThis implementation follows the approach I described, ensuring that every step is clear and understandable in a conversational manner.\n\n```C++ []\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        int patches = 0;\n        int index = 0;\n        long long nextSum = 1;\n\n        while (nextSum <= n) {\n            if (index < nums.size() && nums[index] <= nextSum) {\n                nextSum += nums[index++];\n            } else {\n                nextSum += nextSum;\n                patches++;\n            }\n        }\n\n        return patches;\n    }\n};\n\n```\n\n```Java []\nclass Solution {\n    public int minPatches(int[] nums, int n) {\n        int count = 0;\n        long missing = 1;\n        int i = 0;\n        \n        while (missing <= n) {\n            if (i < nums.length && nums[i] <= missing) {\n                missing += nums[i++];\n            } else {\n                missing += missing;\n                count++;\n            }\n        }\n        \n        return count;\n    }\n}\n\n```\n```Python3 []\nclass Solution:\n    def minPatches(self, nums: List[int], n: int) -> int:\n        count = 0\n        missing = 1\n        i = 0\n        \n        while missing <= n:\n            if i < len(nums) and nums[i] <= missing:\n                missing += nums[i]\n                i += 1\n            else:\n                missing += missing\n                count += 1\n        \n        return count\n\n```\n```JavaScript []\n/**\n * @param {number[]} nums\n * @param {number} n\n * @return {number}\n */\nvar minPatches = function(nums, n) {\n    let count = 0;\n    let missing = 1;\n    let i = 0;\n    \n    while (missing <= n) {\n        if (i < nums.length && nums[i] <= missing) {\n            missing += nums[i++];\n        } else {\n            missing += missing;\n            count++;\n        }\n    }\n    \n    return count;\n};\n\n```\n\n\nThank you for exploring this solution! I hope it helped clarify the problem. \n### Please feel free to upvote if you found it useful. Happy coding!\n
['Greedy', 'C++', 'Java', 'Python3', 'JavaScript']