# Patching Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/patching-array)
Canonical: https://scaleengineer.com/dsa/problems/patching-array
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [Snowflake](https://scaleengineer.com/companies/snowflake)
---
## Problem
Given a sorted integer array `nums` and an integer `n`, add/patch elements to the array such that any number in the range `[1, n]` inclusive can be formed by the sum of some elements in the array.

Return _the minimum number of patches required_.

**Example 1:**

**Input:** nums = [1,3], n = 6
**Output:** 1
Explanation:
Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].
Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].
So we only need 1 patch.

**Example 2:**

**Input:** nums = [1,5,10], n = 20
**Output:** 2
Explanation: The two patches can be [2, 4].

**Example 3:**

**Input:** nums = [1,2,2], n = 5
**Output:** 0

**Constraints:**

* `1 <= nums.length <= 1000`
* `1 <= nums[i] <= 104`
* `nums` is sorted in **ascending order**.
* `1 <= n <= 231 - 1`

# Approaches
## Iterative Sum Generation
This approach simulates the process directly. It first calculates all possible sums that can be formed from the initial `nums` array. Then, it iteratively finds the smallest number `miss` in the range `[1, n]` that cannot be formed. It "patches" the array by adding `miss` to the set of numbers and re-calculates all possible sums. This process repeats until all numbers from `1` to `n` can be formed. The number of patches added is the result.
**Time:** O(P * K * S), where `P` is the number of patches, `K` is the number of elements in the array (which grows with patches), and `S` is the number of reachable sums. This complexity is very high and will lead to a "Time Limit Exceeded" error on typical contest platforms for the given constraints. · **Space:** O(S), where S is the number of unique reachable sums. In the worst case, S can be on the order of `n`. For a large `n`, this would require an enormous amount of memory, making it impractical.
**Pros:** Conceptually straightforward and easy to understand.; Directly models the problem statement of forming sums.
**Cons:** Extremely inefficient in both time and space.; Infeasible for the given constraints on `n` (up to 2^31 - 1) due to memory and time limits.; Recomputes all subset sums from scratch after every single patch, which is highly redundant.
### Explanation
This method attempts to solve the problem by explicitly generating all possible subset sums. It starts with the given numbers and iteratively enhances the set of numbers with patches.

- We maintain a list of numbers, `currentNums`, which initially contains the elements of `nums`.
- We also maintain a count of patches, initialized to 0.
- The main loop continues as long as we haven't covered the entire range `[1, n]`.
- Inside the loop:
    1.  We use a `Set` called `reachableSums` to store all unique sums that can be formed from `currentNums`. We initialize it with `0` (representing the sum of an empty subset).
    2.  We iterate through each number in `currentNums`. For each number, we iterate through the current `reachableSums` and add the number to each sum, adding the new results back to the set. This is essentially a dynamic programming approach to the subset sum problem.
    3.  After generating all sums, we find the smallest integer `miss` from `1` to `n` that is not in `reachableSums`.
    4.  If no such `miss` exists, it means we can form all numbers up to `n`, so we break the loop and return the patch count.
    5.  If a `miss` is found, we need to patch. We add `miss` to our `currentNums`, increment the patch count, and start the next iteration of the main loop.

This approach is conceptually simple but computationally expensive, especially for large `n`, as the size of `reachableSums` can grow very large, and the process of generating sums is repeated for each patch.

```java
import java.util.HashSet;
import java.util.Set;
import java.util.ArrayList;
import java.util.List;

class Solution {
    // This solution is too slow and will cause Time Limit Exceeded (TLE).
    public int minPatches(int[] nums, int n) {
        int patches = 0;
        List<Integer> currentNums = new ArrayList<>();
        for (int num : nums) {
            currentNums.add(num);
        }

        while (true) {
            Set<Long> reachableSums = new HashSet<>();
            reachableSums.add(0L);

            for (int num : currentNums) {
                Set<Long> newSums = new HashSet<>();
                for (long sum : reachableSums) {
                    if (sum + num <= n) {
                        newSums.add(sum + num);
                    }
                }
                reachableSums.addAll(newSums);
            }

            long miss = -1;
            for (long i = 1; i <= n; i++) {
                if (!reachableSums.contains(i)) {
                    miss = i;
                    break;
                }
            }

            if (miss == -1) {
                // All numbers from 1 to n are reachable
                break;
            }

            // Patch with the smallest missing number
            patches++;
            currentNums.add((int)miss);
        }

        return patches;
    }
}
```
### Algorithm
- 1. Initialize `patches = 0` and a list `currentNums` with elements from the input `nums`.
- 2. Start an infinite loop that breaks only when all numbers in `[1, n]` are formable.
- 3. Inside the loop, create a `Set<Long>` called `reachableSums` to store all unique sums, initialized with `0`.
- 4. Iterate through each `num` in `currentNums`. For each `num`, create a temporary set of new sums by adding `num` to every existing sum in `reachableSums`. Add these new sums back to `reachableSums`.
- 5. After generating all possible sums, iterate from `1` to `n` to find the smallest integer `miss` that is not present in `reachableSums`.
- 6. If no such `miss` is found, it means all numbers in `[1, n]` are covered. Break the loop.
- 7. If a `miss` is found, it means we need to patch the array. Increment `patches`, add `miss` to `currentNums`, and continue to the next iteration of the main loop to re-evaluate the reachable sums.
- 8. Finally, return the total `patches` count.

## Greedy Approach
This is an efficient and optimal approach based on a greedy strategy. The core idea is to keep track of the maximum number, let's call it `reachable`, such that all integers in the range `[1, reachable]` can be formed by sums of elements from the (patched) array. We iterate through the numbers and patches, always aiming to extend this `reachable` range as much as possible until it covers `n`.
**Time:** O(m + log n), where `m` is the length of `nums`. The `while` loop continues as long as `miss <= n`. In each iteration, either the pointer `i` is incremented (which can happen at most `m` times) or `miss` is at least doubled (which can happen at most `log n` times). Therefore, the total number of iterations is bounded by `m + log n`. · **Space:** O(1). We only use a few variables (`miss`, `patches`, `i`) to keep track of the state, requiring constant extra space regardless of the input size.
**Pros:** Highly efficient with a linear time complexity relative to the input size.; Optimal solution for this problem.; Requires constant extra space, making it very memory-efficient.; The logic is simple and elegant once the greedy property is understood.
**Cons:** The greedy logic, while simple once understood, might not be immediately obvious to come up with.
### Explanation
The key insight for this problem is to think about the range of sums we can form. Let's say we can form every integer sum in the range `[1, k]`. What's the next number we need to be able to form? It's `k + 1`. 

We can maintain a variable, let's call it `miss`, which is the smallest integer that we cannot form with the numbers we've considered so far. Initially, `miss` is `1`.

We then iterate while `miss <= n`:
- If we have a number `num` in our array such that `num <= miss`, we can use it. By taking this `num` and adding it to all the sums we could already form (which is the range `[1, miss - 1]`), we can now form sums up to `(miss - 1) + num`. This means our new `miss` becomes `miss + num`.
- If the next number in our array is greater than `miss`, or we have no more numbers, we can't form `miss`. To fix this, we must add a patch. To be as efficient as possible, we should add a patch that extends our reachable range the furthest. The best number to add is `miss` itself. If we patch with `miss`, our reachable range `[1, miss - 1]` extends to `[1, (miss - 1) + miss]`. So, our new `miss` becomes `miss + miss`. We increment our patch counter for this action.

This greedy choice is optimal because adding any number smaller than `miss` would result in a smaller extension of our reachable range. Adding a number larger than `miss` would still leave `miss` unreachable.

We use a `long` for `miss` to avoid integer overflow since `n` can be large and `miss` can grow up to `n`.

```java
class Solution {
    public int minPatches(int[] nums, int n) {
        long miss = 1; // Represents the smallest sum that cannot be formed.
        int patches = 0;
        int i = 0;

        while (miss <= n) {
            if (i < nums.length && nums[i] <= miss) {
                // If the current number in nums can help us form 'miss',
                // we use it. This extends our reachable range from [1, miss-1]
                // to [1, miss-1 + nums[i]].
                miss += nums[i];
                i++;
            } else {
                // If the current number is too large or we've run out of numbers,
                // we must patch. The most efficient patch is 'miss' itself.
                // This extends our reachable range from [1, miss-1]
                // to [1, miss-1 + miss].
                miss += miss;
                patches++;
            }
        }
        return patches;
    }
}
```
### Algorithm
- 1. Initialize `miss = 1L` (a `long` to prevent overflow). This variable represents the smallest sum that we cannot currently form.
- 2. Initialize `patches = 0` to count the number of added elements.
- 3. Initialize `i = 0` as a pointer for the `nums` array.
- 4. Loop as long as `miss <= n`. This condition ensures we continue until we can form all numbers up to `n`.
- 5. Inside the loop, check if the current number `nums[i]` (if available) is less than or equal to `miss`.
- 6. **Case 1: `nums[i] <= miss`**. If the condition is true, it means we can use `nums[i]` to extend our reach. Since we can already form all sums up to `miss - 1`, adding `nums[i]` allows us to form all sums up to `(miss - 1) + nums[i]`. We update `miss` to `miss + nums[i]` and advance our pointer `i`.
- 7. **Case 2: `nums[i] > miss` or `i` is out of bounds**. We cannot form `miss` using the available numbers. We must add a patch. The most effective patch is `miss` itself. Adding `miss` extends our reachable range to `(miss - 1) + miss`. We update `miss` to `miss + miss` and increment `patches`.
- 8. After the loop terminates (when `miss > n`), return the total `patches`.

# Solutions
### Java

```java
class Solution {
public
  int minPatches(int[] nums, int n) {
    long x = 1;
    int ans = 0;
    for (int i = 0; x <= n;) {
      if (i < nums.length && nums[i] <= x) {
        x += nums[i++];
      } else {
        ++ans;
        x <<= 1;
      }
    }
    return ans;
  }
}

```

### Python

```python
class Solution:
    def minPatches(self, nums: List[int], n: int) -> int: x = 1 ans = i = 0 while x <= n: if i < len(nums) and nums[i] <= x: x += nums[i] i += 1 else: ans += 1 x <<= 1 return ans

```

### CPP

```cpp
class Solution {
public:
  int minPatches(vector<int> &nums, int n) {
    long long x = 1;
    int ans = 0;
    for (int i = 0; x <= n;) {
      if (i < nums.size() && nums[i] <= x) {
        x += nums[i++];
      } else {
        ++ans;
        x <<= 1;
      }
    }
    return ans;
  }
};

```