Patching Array - Solution Explanation and Code (Video Solution Available)
Video SolutionIntuitionTo cover all numbers in the range [1, n] using the given array nums, we need to ensure that every integer in the range can be formed as t
# Video Solution
[https://youtu.be/3XvfM0fOnjc?si=hz58mAXHPF62vVxq]()
# Intuition
To cover all numbers in the range `[1, n]` using the given array `nums`, we need to ensure that every integer in the range can be formed as the sum of one or more elements from `nums`. If `nums` lacks certain values necessary to achieve this, we can "patch" the array by adding new numbers.

The key idea is to track the smallest number `miss` that we cannot form using the current elements of `nums` and any previously added patches. If a number in `nums` can contribute to forming `miss`, we use it. Otherwise, we add `miss` as a patch and update `miss`.

# Approach
1. **Initialize variables**:
   - `miss` starts at 1, representing the smallest number we cannot yet form.
   - `result` counts the patches added.
   - `i` is the index for traversing `nums`.

2. **Iterate while `miss <= n`**:
   - If `nums[i] <= miss`, add `nums[i]` to `miss` (i.e., we can now form numbers up to `miss + nums[i]`) and increment `i`.
   - Otherwise, add `miss` as a patch. This ensures we can form numbers up to `2 * miss`.

3. **Repeat until `miss > n`**:
   - At this point, all numbers in `[1, n]` are covered, and we return the number of patches.

# Complexity
- **Time complexity**:
  $$O(m + \log n)$$, where `m` is the length of `nums`. Traversing `nums` takes $$O(m)$$, and each patch approximately doubles `miss`, leading to $$O(\log n)$$ iterations for patches.

- **Space complexity**:
  $$O(1)$$, as we use constant extra space.

# Code
```java []
class Solution {
    public int minPatches(int[] nums, int n) {
        long miss = 1;
        int result = 0;
        int i = 0;

        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) {
                miss += nums[i];
                i++;
            } else {
                miss += miss;
                result++;
            }
        }

        return result;
    }
}
['Java']