Patching Array
Problem
Given a sorted array nums and an integer n, return the minimum number of patches (additional numbers) needed so every value in [1, n] is representable as a sum of some subset of the array.
nums = [1,3], n = 61def min_patches(nums, n):
miss = 1
i = patches = 0
while miss <= n:
if i < len(nums) and nums[i] <= miss:
miss += nums[i]; i += 1
else:
miss += miss; patches += 1
return patchesfunction minPatches(nums, n) {
let miss = 1n, patches = 0, i = 0, N = BigInt(n);
while (miss <= N) {
if (i < nums.length && BigInt(nums[i]) <= miss) {
miss += BigInt(nums[i]); i++;
} else {
miss += miss; patches++;
}
}
return patches;
}class Solution {
public int minPatches(int[] nums, int n) {
long miss = 1; int i = 0, patches = 0;
while (miss <= n) {
if (i < nums.length && nums[i] <= miss) { miss += nums[i]; i++; }
else { miss += miss; patches++; }
}
return patches;
}
}int minPatches(vector& nums, int n) {
long long miss = 1;
int i = 0, patches = 0;
while (miss <= n) {
if (i < (int)nums.size() && (long long)nums[i] <= miss) { miss += nums[i]; i++; }
else { miss += miss; patches++; }
}
return patches;
} Explanation
The clean idea is to track a single value miss = the smallest sum we cannot yet build. A neat fact: if we can already make every total from 1 up to miss - 1, then once we add some number x (with x <= miss), we can suddenly make everything up to miss + x - 1. The reachable range just grows.
We walk through the sorted array. If the current number nums[i] is useful (nums[i] <= miss), it slots right in and extends our reach: miss += nums[i]. We don't spend a patch — we use what's given.
If the next array number is too big (or we've run out), there is a gap exactly at miss. The best possible patch is to add miss itself, which doubles the reach to 2 * miss — no other single number covers more. We do that and count one patch.
We repeat until miss exceeds n, meaning all of [1, n] is covered, and return the patch count.
Example: nums = [1, 3], n = 6. Start miss = 1. The 1 fits, reach grows to 2. Now 3 > 2, so patch in 2 (one patch), reach jumps to 4. Then 3 <= 4 fits, reach becomes 7 > 6. Done with 1 patch.