Patching Array

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

class Solution:
    def minPatches(self, nums: list[int], n: int) -> int:
        patches = 0
        reachable = 0
        i = 0
        
        while reachable < n:
            if i < len(nums) and nums[i] <= reachable + 1:
                reachable += nums[i]
                i += 1
            else:
                reachable += reachable + 1
                patches += 1
        
        return patches

Explanation:

The idea is to keep track of the maximum reachable number reachable. If the next number in nums is less than or equal to reachable + 1, we can simply add it to reachable and increment the index i. If not, we need to patch the array by adding reachable + 1 to it. This increases the reachable number to reachable + (reachable + 1) = 2 * reachable + 1.

Example:

Let's say nums = [1, 3] and n = 6.

1. reachable = 0, i = 0, patches = 0
2. Since nums[0] = 1 <= reachable + 1 = 1, reachable = 1, i = 1
3. Since nums[1] = 3 > reachable + 1 = 2, we need to patch with reachable + 1 = 2. So patches = 1, reachable = 1 + 2 = 3
4. Since nums[1] = 3 <= reachable + 1 = 4, reachable = 3 + 3 = 6, i = 2
5. Since reachable = 6 >= n = 6, we return patches = 1

Complexity Analysis:

• Time Complexity: O(m + log n), where m is the length of nums. We iterate through the input array once, and in the worst case, we might need log n patches, leading to the O(log n) component. Because the sorted nums array is of length m, the overall time complexity becomes O(m + log n).
• Space Complexity: O(1). We only use a constant amount of extra space.