# 按要求补齐数组
给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。
示例 1:
输入: nums = [1,3], n = 6
输出: 1
解释:
根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。
现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。
其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。
所以我们最少需要添加一个数字。
示例 2:
输入: nums = [1,5,10], n = 20
输出: 2
解释: 我们需要添加 [2, 4]。
示例 3:
输入: nums = [1,2,2], n = 5
输出: 0
以下错误的选项是？
## aop
### before
```c
#include
using namespace std;
```
### after
```c
int main()
{
Solution sol;
vector nums = {1, 5, 10};
int n = 20;
int res = sol.minPatches(nums, n);
cout << res;
return 0;
}
```
## 答案
```c
class Solution
{
public:
int minPatches(vector &nums, int n)
{
long sum = 0;
int reti = 0;
int i = 0;
while (sum < n)
{
if (i >= nums.size())
break;
if ((sum + 1) >= nums[i])
{
sum += nums[++i];
}
else
{
int temp = sum + 1;
sum += temp;
reti++;
}
}
while (sum < n)
{
int temp = sum + 1;
sum += temp;
}
return reti;
}
};
```
## 选项
### A
```c
class Solution
{
public:
int minPatches(vector &nums, int n)
{
int resultCnt = 0;
int numsSize = nums.size(), index = 0;
long long head = 1;
while (head <= n)
{
if (index < numsSize && nums[index] <= head)
{
head += nums[index++];
}
else
{
head += head;
resultCnt += 1;
}
}
return resultCnt;
}
};
```
### B
```c
class Solution
{
public:
int minPatches(vector &nums, int n)
{
int patchCount = 0, i = 0;
long miss = 1;
while (miss <= n)
{
if (i < nums.size() && miss >= nums[i])
miss += nums[i++];
else
{
patchCount++;
miss = miss * 2;
}
}
return patchCount;
}
};
```
### C
```c
class Solution
{
public:
int minPatches(vector &nums, int n)
{
int len = nums.size(), i = 0;
long current_coverage = 0;
int ans = 0;
while (current_coverage < n)
{
if (i < len)
{
if (nums[i] <= current_coverage + 1)
{
current_coverage += nums[i];
i++;
}
else
{
ans++;
current_coverage += current_coverage + 1;
}
}
else
{
ans++;
current_coverage += current_coverage + 1;
}
}
return ans;
}
};
```