C++ में 1 से K तक की सभी संख्याएँ बनाने के लिए कितनी संख्याएँ जोड़नी होंगी, इसकी गणना करने वाला प्रोग्राम

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है और एक मान k है। हमें nums में डालने के लिए आवश्यक न्यूनतम संख्याओं की संख्या ज्ञात करनी है ताकि हम nums में किसी सबसेट का उपयोग करके [1, k] रेंज की कोई भी संख्या बना सकें।

उदाहरण के लिए, यदि इनपुट है nums = [3, 5], k = 6, तो आउटपुट 2 होगा, क्योंकि हमें 1, 2 डालने होंगे, ताकि हम बना सकें: 1 = [1], 2 = [2], 3 = [3], 4 = [1, 3], 5 = [5], 6 = [1, 5]।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

1. सरणी nums को सॉर्ट करें।
2. sum := 0, next := 1, ret := 0 आरंभ करें।
3. nums में प्रत्येक i के लिए:
   • जब next < i हो, तब तक:
     • यदि sum >= k, तो लूप से बाहर निकलें।
     • sum := sum + next
     • next := sum + 1
     • ret को 1 बढ़ाएँ।
   • यदि sum >= k, तो लूप से बाहर निकलें।
   • sum := sum + i
   • next := sum + 1
4. जब next <= k हो, तब तक:
   • sum := sum + next
   • next := sum + 1
   • ret को 1 बढ़ाएँ।
5. ret लौटाएँ।

C++ कार्यान्वयन

#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 main() {
    vector<int> v = {3, 5};
    int k = 6;
    cout << solve(v, k);
    return 0;
}

इनपुट

[3, 5], 6

आउटपुट

2