Mảng vá trong C ++

Giả sử chúng ta có một số mảng và một số. Chúng ta có thể thêm các phần tử trong mảng, sao cho bất kỳ số nào trong phạm vi [1, n] (cả hai đều bao hàm) có thể được tạo thành bằng tổng của một số phần tử trong mảng. Chúng tôi phải tìm số lượng bản vá yêu cầu tối thiểu. Vì vậy, khi mảng giống như [1,4] và số đã cho là n =7, thì đầu ra sẽ là 1, như ban đầu các số là [1], [4] và [1,4] =5, bây giờ nếu chúng ta thêm 2 thành mảng, sau đó các số sẽ là [1], [2], [4], [1,2], [1,4], [2,4], [1,2,4], do đó tổng các giá trị sẽ lần lượt là 1, 2, 4, 3, 5, 6, 7.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

req:=1, i:=0, ret:=0
while req <=n, do -
- nếu tôi
  - req =req + nums [i]
  - tăng tôi lên 1
- Nếu không
  - req =req + req
  - tăng ret lên 1
trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

{1,4}

Mảng vá trong C ++

Ví dụ

Đầu vào

Đầu ra