Easy Java Solution | Greedy | Beats 100 💯✅
Min Patches Problem\n\n## Problem Description\n\nGiven a sorted integer array nums and a positive integer n, your goal is to compute the minimum number of patch
# Min Patches Problem\n\n## Problem Description\n\nGiven a sorted integer array `nums` and a positive integer `n`, your goal is to compute the minimum number of patches required to ensure that every integer in the range `[1, n]` can be formed as a sum of some elements from `nums`. A patch is an integer that you can add to `nums`.\n\n## Intuition\n\nTo solve this problem efficiently, we need to ensure that we can generate all numbers in the range `[1, n]` using the elements in `nums` and a minimal number of additional patches. The key insight is to track the smallest number that we cannot form (`miss`). Initially, `miss` is `1`, meaning we need to form the number `1` first. If the smallest number in `nums` that we haven\'t used yet is less than or equal to `miss`, we can use it to extend our range of representable sums. If it is greater than `miss`, we must add `miss` itself as a patch to extend our range.\n\nThe approach ensures that at each step, we either extend our range of representable sums using existing elements from `nums` or we add a new patch that extends the range significantly. This greedy strategy minimizes the number of patches needed.\n\n## Approach\n\n1. **Initialize**:\n    - `patches` to `0` to count the number of patches added.\n    - `i` to `0` to iterate through `nums`.\n    - `miss` to `1` which is the smallest number that cannot be formed.\n\n2. **Iterate while `miss` is less than or equal to `n`**:\n    - If `i` is within the bounds of `nums` and `nums[i]` is less than or equal to `miss`:\n        - Add `nums[i]` to `miss`.\n        - Increment `i`.\n    - Otherwise, add `miss` itself as a patch.\n        - Double `miss` to extend the range significantly.\n        - Increment the `patches` count.\n\n3. **Return the total number of patches**.\n\nThis process continues until `miss` exceeds `n`, ensuring that every number up to `n` can be formed.\n\n## Time Complexity\n\nThe time complexity is **O(m)**, where `m` is the length of `nums`. This is because we iterate through the elements of `nums` at most once, and each patch operation is essentially a constant time operation relative to `nums`.\n\n## Space Complexity\n\nThe space complexity is **O(1)**. The algorithm uses a fixed amount of additional space for variables regardless of the size of `nums` or `n`.\n\n\n# Code\n```\nclass Solution {\n    public int minPatches(int[] nums, int n) {\n        int patches = 0;\n        int i = 0;\n        long miss = 1;\n        while(miss <= n) {\n            if(i < nums.length && nums[i] <= miss)\n                miss += nums[i++];\n            else {\n                miss += miss;\n                patches++;\n            }\n        }\n        return patches;\n    }\n}\n```
['Array', 'Math', 'Greedy', 'Java']