Intuitive Approach with Observation and Dry Run ✅💯
Minimum Number of Patches\n\n## Problem Statement\nGiven a sorted array of positive integers nums and an integer n, you need to add the minimum number of patche
# Minimum Number of Patches\n\n## Problem Statement\nGiven a sorted array of positive integers `nums` and an integer `n`, you need to add the minimum number of patches to the array such that every number in the range `[1, n]` can be formed by the sum of some elements in the array.\n\n## Intuition\nTo solve the problem, we can use a greedy algorithm. The goal is to ensure that for every integer up to `n`, we can form it using the elements of the array `nums` and any additional patches we add.\n\n## Approach\n1. **Initialize Variables**:\n   - `patches`: A counter to keep track of the number of patches added.\n   - `maxReach`: A variable to track the maximum number we can form using the numbers in `nums` and the patches added so far.\n   - `i`: An index to iterate over the array `nums`.\n\n2. **Iterate Until the Range is Covered**:\n   - While `maxReach` is less than `n`:\n     - If the current element in `nums` can extend the range (`maxReach + 1 >= nums[i]`), use it and update `maxReach`.\n     - If the current element in `nums` cannot be used, add a patch (the number `maxReach + 1`) and update `maxReach`.\n\n3. **Return the Result**:\n   - Once the loop ends, `patches` will contain the minimum number of patches required to ensure the range from `1` to `n` can be formed.\n## Dry Run\nGiven `nums = [1, 5, 10]` and `n = 20`:\n\n- **Initial State**:\n  - `patches = 0`\n  - `maxReach = 0`\n  - `i = 0`\n\n- **Iteration 1**:\n  - `maxReach + 1 = 1`, `nums[i] = 1` (1 can be used)\n  - Update `maxReach = maxReach + nums[i] = 0 + 1 = 1`\n  - Increment `i = 1`\n  - `patches = 0`\n  \n- **Iteration 2**:\n  - `maxReach + 1 = 2`, `nums[i] = 5` (2 cannot be formed with current `maxReach`)\n  - Add patch `2`\n  - Update `maxReach = maxReach + (maxReach + 1) = 1 + 2 = 3`\n  - `patches = 1`\n\n- **Iteration 3**:\n  - `maxReach + 1 = 4`, `nums[i] = 5` (4 cannot be formed with current `maxReach`)\n  - Add patch `4`\n  - Update `maxReach = maxReach + (maxReach + 1) = 3 + 4 = 7`\n  - `patches = 2`\n\n- **Iteration 4**:\n  - `maxReach + 1 = 8`, `nums[i] = 5` (5 can be used)\n  - Update `maxReach = maxReach + nums[i] = 7 + 5 = 12`\n  - Increment `i = 2`\n  - `patches = 2`\n\n- **Iteration 5**:\n  - `maxReach + 1 = 13`, `nums[i] = 10` (10 can be used)\n  - Update `maxReach = maxReach + nums[i] = 12 + 10 = 22`\n  - Increment `i = 3`\n  - `patches = 2`\n\n- **End Condition**:\n  - `maxReach = 22`, which is greater than `n = 20`\n  - Total patches added = 2\n\nThus, the minimum number of patches required is `2`.\n\n\n## Complexity\n- **Time Complexity**: \\(O(max(m, lon(n)))\\), where \\(m\\) is the number of elements in the input array `nums`. This is because each element is processed at most once.\n- **Space Complexity**: \\(O(1)\\), as we are using a constant amount of extra space regardless of the input size.\n\n## Code\n```cpp\nclass Solution {\npublic:\n    int minPatches(vector<int>& nums, int n) {\n        long long patches = 0, maxReach = 0;\n        int i = 0;\n\n        while (maxReach < n) {\n            if (i < nums.size() && maxReach + 1 >= nums[i]) {\n                maxReach += nums[i];\n                i++;\n            } else {\n                patches++;\n                maxReach += (maxReach + 1);\n            }\n        }\n\n        return patches;\n    }\n};\n```
['Array', 'Greedy', 'C++']