C++ এ প্যাচিং অ্যারে

ধরুন আমাদের একটি অ্যারে সংখ্যা এবং একটি সংখ্যা আছে। আমরা অ্যারেতে উপাদান যোগ করতে পারি, যেমন রেঞ্জের যে কোনো সংখ্যা [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, do −
- যদি i <সংখ্যা এবং সংখ্যার আকার[i] <=req, তারপর,
  - req =req + সংখ্যা[i]
  - i 1 দ্বারা বাড়ান
- অন্যথায়
  - req =req + req
  - 1 দ্বারা 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}