330. Patching Array

[mah-shamim]

Topics: Array, Greedy

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
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

[mah-shamim]

We need to ensure that every number in the range [1, n] can be formed by the sum of some elements in the given array. We can use a greedy algorithm to determine the minimum number of patches required.

Solution Explanation:

1. Key Insight:

   • Start with the smallest missing number miss which starts at 1.
   • Iterate through the array nums. If the current number in nums is less than or equal to miss, then miss can be covered by adding this number. Otherwise, we need to patch miss to the array, effectively doubling the range that can be covered.

2. Algorithm:

   • Initialize miss = 1 and patches = 0.
   • Loop through the array while miss <= n:
     • If the current number in nums can cover miss, move to the next number in nums.
     • If the current number is greater than miss, patch miss and double the range covered by setting miss = miss * 2.
   • Continue until the entire range [1, n] is covered.

3. Complexity:

• The time complexity is O(m + log n), where m is the size of the array nums.

Let's implement this solution in PHP: 330. Patching Array

<?php
/**
* @param String $n
* @return String
*/
function minPatches($nums, $n) {
  $ans = 0; // Number of patches added
  $i = 0;  // Index in the array nums
  $miss = 1; // The smallest number that we can't form yet
  while ($miss <= $n) {
    if ($i < count($nums) && $nums[$i] <= $miss) {
      // If nums[i] is within the range we need to cover
      $miss += $nums[$i++];
    } else {
      // If nums[i] is greater than the current miss, we need to patch
      $miss += $miss;  // Add `miss` itself to cover the missing number
      ++$ans;
    }
  }
  return $ans;
}

// Example usage:

// Example 1
$nums1 = [1, 3];
$n1 = 6;
echo minPatches($nums1, $n1); // Output: 1

// Example 2
$nums2 = [1, 5, 10];
$n2 = 20;
echo minPatches($nums2, $n2); // Output: 2

// Example 3
$nums3 = [1, 2, 2];
$n3 = 5;
echo minPatches($nums3, $n3); // Output: 0
?>

Explanation:

• Initial Setup: We initialize miss as 1, meaning we want to ensure we can generate the number 1.
• While Loop: We loop until miss exceeds n (the maximum number we need to cover). In each iteration:
  • If the current number in nums can help cover miss, we add it to miss and move to the next number.
  • If not, we "patch" the array by effectively adding miss to it (without changing the array itself) and then update miss to cover the new range.
• Output: The total number of patches required is returned.

This algorithm ensures that we cover the entire range [1, n] with the minimum number of patches.

[kovatz]

Thanks to solve the problem of patching an array

[mah-shamim]

Thanks