Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example:

nums = [1, 5, 10], n = 20

Return 2.

The two patches can be [2, 4]

用一个例子说明思路：

nums = [1, 2, 4, 13, 43], n = 100

miss — Smallest miss sum, i.e. sum in the range [0, miss) has been reached

miss = 1, nums[0] = 1, [0, 2) can be reached, miss -> 2

miss = 2, nums[1] = 2, [0, 4) can be reached, miss -> 4

miss = 4, nums[2] = 4, [0, 8) can be reached, miss -> 8

miss = 8, nums[3] = 13, add 8, [0, 16) can be reached, miss -> 16

miss = 16, nums[3] = 13, [0, 29) can be reached, miss -> 29

miss = 29, nums[4] = 43, add 29, [0, 58) can be reached, miss -> 58

miss = 58, nums[4] = 43, [0, 101) can be reached, miss -> 101 > 100

Added 2 numbers in total

public int minPatches(int[] nums, int n) {
long miss = 1; // n = Integer.MAX_VALUE时会用到long
int i = 0, count = 0;
while (miss <= n) {
if (i < nums.length && nums[i] <= miss) {
miss += nums[i++];
} else {
count++;
miss += miss;
}
}
return count;
}

### Like this:

Like Loading...