用C ++修补数组

假设我们有一个数组nums和一个数字。我们可以在数组中添加元素，以便可以由数组中某些元素的总和形成[1，n]范围内的任何数字（包括两端）。我们必须找到所需补丁的最小数量。因此，当数组类似于[1,4]且给定数字为n = 7时，输出将为1，因为最初的数字为[1]，[4]和[1,4] = 5，如果我们将2变成数组，则数字将为[1]，[2]，[4]，[1,2]，[1,4]，[2,4]，[1,2,4]，因此总和值分别为1、2、4、3、5、6、7。

为了解决这个问题，我们将遵循以下步骤-

• req：= 1，i：= 0，ret：= 0

• 当req <= n时，执行-

• 需求=需求+需求

• 增加ret 1

• req = req +数字[i]

• 使我增加1

• 如果i <nums和nums [i] <= req的大小，则，

• 除此以外

• 返回ret

示例

让我们看下面的实现以更好地理解-

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int minPatches(vector<int>& nums, int n) {
      long long int req = 1;
      int i = 0;
      int ret = 0;
      while(req <= n){
         if(i < nums.size() && nums[i] <= req){
            req += nums[i];
            i++;
         } else {
            req += req;
            ret++;
         }
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,4};
   cout << (ob.minPatches(v, 7));
}

输入值

{1,4}

输出结果

1