C++ এ 1 থেকে k পর্যন্ত সমস্ত সংখ্যা তৈরি করতে কতগুলি সংখ্যা যুক্ত করতে হবে তা গণনা করার প্রোগ্রাম

ধরুন আমাদের কাছে সংখ্যার একটি তালিকা আছে যার নাম nums এবং আরেকটি মান k। আমাদের সংখ্যার মধ্যে ন্যূনতম সংখ্যার সংখ্যা খুঁজে বের করতে হবে যা আমাদের সংখ্যায় সন্নিবেশ করতে হবে যাতে আমরা সংখ্যার কিছু উপসেট ব্যবহার করে [1, k] থেকে যেকোনো সংখ্যা তৈরি করতে পারি।

সুতরাং, ইনপুট যদি nums =[3, 5], k =6 এর মত হয়, তাহলে আউটপুট হবে 2, যেমন আমাদের 1, 2 সন্নিবেশ করতে হবে, তাই আমরা করতে পারি:1 =[1], 2 =[2 ], 3 =[3], 4 =[1, 3], 5 =[5], 6 =[1, 5]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• অ্যারের সংখ্যা সাজান
• সমষ্টি :=0, পরবর্তী :=1, ret :=0
• সকলের জন্য আমি সংখ্যায়
  • যখন পরবর্তী
  • যদি যোগফল>=k হয়, তাহলে:
    • লুপ থেকে বেরিয়ে আসুন
  • সমষ্টি :=যোগফল + পরবর্তী
  • পরবর্তী :=যোগফল + 1
  • (রেট 1 দ্বারা বৃদ্ধি করুন)
• যদি যোগফল>=k হয়, তাহলে:
  • লুপ থেকে বেরিয়ে আসুন
• সমষ্টি :=যোগফল + i
• পরবর্তী :=যোগফল + 1

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include
using namespace std;
class Solution {
   public:
   int solve(vector& nums, int k) {
      sort(nums.begin(), nums.end());
      int sum = 0;
      int next = 1;
      int ret = 0;
      for (int i : nums) {
         while (next < i) {
            if (sum >= k) break;
            sum += next;
            next = sum + 1;
            ret++;
         }
         if (sum >= k) break;
         sum += i;
         next = sum + 1;
      }
      while (next <= k) {
         sum += next;
         next = sum + 1;
         ret++;
      }
      return ret;
   }
};

int solve(vector& nums, int k) {
   return (new Solution())->solve(nums, k);
}

int main(){
   vector v = {3, 5};
   int k = 6;
   cout << solve(v, k);
}

ইনপুট

[3, 5], 6

আউটপুট

2