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

ধরি আমাদের একটি সংখ্যা তালিকা আছে যার নাম nums এবং আরেকটি মান k। আমাদের লক্ষ্য হলো nums-এ ন্যূনতম কতগুলো সংখ্যা যোগ করতে হবে যাতে nums-এর যেকোনো সাবসেট ব্যবহার করে ১ থেকে k পর্যন্ত যেকোনো সংখ্যা তৈরি করা যায়।

উদাহরণস্বরূপ, ইনপুট যদি nums = [3, 5] এবং k = 6 হয়, তবে আউটপুট হবে 2, কারণ আমাদের ১ এবং ২ যোগ করতে হবে। এরপর আমরা बना পারি: ১ = [১], ২ = [২], ৩ = [৩], ৪ = [১, ৩], ৫ = [৫], ৬ = [১, ৫]।

সমাধানের ধাপসমূহ:

nums অ্যারে সাজান (sort করুন)
sum := 0, next := 1, ret := 0 ইনিশিয়ালাইজ করুন
nums-এর প্রতিটি উপাদান i এর জন্য:
- যখন next < i:
  - যদি sum >= k হয়, তবে লুপ থেকে বের হোন
  - sum := sum + next
  - next := sum + 1
  - ret ১ বাড়ান
- যদি sum >= k হয়, তবে লুপ থেকে বের হোন
- sum := sum + i
- next := sum + 1
যখন next <= k:
- sum := sum + next
- next := sum + 1
- ret ১ বাড়ান
ret রিটার্ন করুন

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<int>& 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<int>& nums, int k) {
    return (new Solution())->solve(nums, k);
}

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

ইনপুট

[3, 5], 6