This problem requires efficiently patching gaps in a sequence formed by a sorted integer array nums
to cover the range [1, n]. Using a greedy algorithm ensures that we always extend the covered range by adding the minimum possible number to target
.
-
Initialization: Start with
target
initialized to 0 andpatches
set to 0 to count how many patches are added. -
Greedy Strategy: Iterate through
nums
to ensuretarget
covers up ton
. For each number innums
:- If the current number is less than or equal to
target + 1
, extendtarget
by adding this number. - If the current number is greater than
target + 1
, add patches to cover the gap using successive increments oftarget + 1
.
- If the current number is less than or equal to
-
Final Gap Handling: After iterating through
nums
, ensure there are no gaps betweentarget
andn
. Add patches to fill this gap using successive increments oftarget + 1
untiltarget
reaches or exceedsn
. -
Return
patches
: Oncetarget
covers the range [1, n], return the total number of patches added.
-
Time complexity: O(m + log n), where
m
is the length ofnums
. This complexity arises from iterating throughnums
and adjustingtarget
. The logarithmic component comes from the operations involvingtarget
and its growth. -
Space complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size, primarily for storing
target
,patches
, and iterating variables.
public class Solution {
public int MinPatches(int[] nums, int n) {
long target = 0l;
int patches = 0;
int index = 0;
while (target < n && index < nums.Length && nums[index] <= n)
{
while (nums[index] > target + 1 && target < n)
{
target += target + 1;
patches++;
}
target += nums[index];
index++;
}
while(target < n)
{
patches++;
target += target + 1;
}
return patches;
}
}