C++에서 배열 패치

배열 숫자와 하나의 숫자가 있다고 가정합니다. 배열에 요소를 추가할 수 있으므로 [1, n] 범위의 모든 숫자(둘 다 포함)는 배열에 있는 일부 요소의 합으로 구성될 수 있습니다. 필요한 패치의 최소 수를 찾아야 합니다. 따라서 배열이 [1,4]와 같고 주어진 숫자가 n =7이면 처음에 숫자가 [1], [4] 및 [1,4] =5이므로 출력은 1이 됩니다. 이제 추가하면 2를 배열에 넣으면 숫자는 [1], [2], [4], [1,2], [1,4],[2,4], [1,2,4]가 되므로 합계 값은 각각 1, 2, 4, 3, 5, 6, 7입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

요청 :=1, 나는 :=0, 재 :=0
req <=n인 동안 −
- if i <숫자와 숫자의 크기[i] <=req, 그러면
  - 요청 =요청 + 숫자[i]
  - i를 1 증가
- 그렇지 않으면
  - 요구 =요구 + 요구
  - ret 1 증가
리턴 렛

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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}