330. Patching Array – Leetcode Solutions

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:
        # Initialize variables
        patches = 0  # This will count how many patches we need
        miss = 1     # The smallest number we cannot form yet
        i = 0        # Pointer for the nums array

        # Iterate until we have covered all numbers from 1 to n
        while miss <= n:
            if i < len(nums) and nums[i] <= miss:
                # If the current number in nums is <= miss, add it to the range
                miss += nums[i]
                i += 1
            else:
                # Otherwise, patch the array by adding 'miss' to the range
                miss += miss
                patches += 1
        
        # Return the total number of patches needed
        return patches

class Solution {
public:
    int minPatches(vector<int>& nums, int n) {
        // Initialize variables
        int patches = 0;  // This will keep track of how many numbers we need to patch
        long long maxReach = 0;  // This will store the largest number we can form so far (starting from 0)
        int i = 0;  // Index to traverse through the nums array

        // While maxReach is less than n, we need to ensure we can form all numbers from 1 to n
        while (maxReach < n) {
            // If the current number in nums is less than or equal to maxReach + 1,
            // we can use it to extend the range of numbers we can form.
            if (i < nums.size() && nums[i] <= maxReach + 1) {
                maxReach += nums[i];  // Extend the maxReach by adding nums[i]
                i++;  // Move to the next number in the array
            } else {
                // If nums[i] is greater than maxReach + 1, we need to patch a new number.
                // The best number to patch is maxReach + 1, as it allows us to extend
                // the range optimally.
                maxReach += maxReach + 1;
                patches++;  // Increment the patch count since we are adding a new number
            }
        }

        return patches;  // Return the total number of patches required
    }
};

var minPatches = function(nums, n) {
    let patches = 0; // Count of patches to be added
    let i = 0; // Pointer for traversing the nums array
    let miss = 1; // The smallest missing number that can't be formed yet

    // Continue until we can form every number in the range [1, n]
    while (miss <= n) {
        if (i < nums.length && nums[i] <= miss) {
            // If the current number in nums can help us form the number 'miss', use it.
            miss += nums[i];
            i++;
        } else {
            // If the current number in nums is too large or we've run out of numbers in nums,
            // patch by adding 'miss' to the array.
            miss += miss;
            patches++; // Increment the patch count
        }
    }

    return patches;
};

class Solution {
    public int minPatches(int[] nums, int n) {
        // 'miss' represents the smallest number that cannot be formed with the current elements
        long miss = 1; // We use long because 'miss' might exceed the range of int when n is large
        int patches = 0; // This will track the number of elements we need to patch (add)
        int i = 0; // Index to iterate over the nums array
        
        // Continue until 'miss' exceeds 'n', meaning we can form all numbers from 1 to n
        while (miss <= n) {
            // If the current element in nums can be used to extend the range we can form
            if (i < nums.length && nums[i] <= miss) {
                // Use nums[i] to extend the range of numbers we can form
                miss += nums[i];
                i++; // Move to the next number in nums
            } else {
                // If nums[i] is greater than 'miss', we need to patch the array by adding 'miss'
                // Add 'miss' to the set of numbers, effectively doubling the range we can form
                miss += miss;
                patches++; // Increment the patch count as we added a number
            }
        }
        
        // Return the total number of patches needed
        return patches;
    }
}