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

मान लीजिए कि हमारे पास संख्याओं की एक सूची है जिसे अंक कहा जाता है और दूसरा मान 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, रिट :=0
• सभी के लिए मैं अंकों में
  • अगले
  • यदि योग>=k, तो:
    • लूप से बाहर आएं
  • योग :=योग + अगला
  • अगला:=योग + 1
  • (रिटर्न 1 से बढ़ाएं)
• यदि योग>=k, तो:
  • लूप से बाहर आएं
• योग :=योग + मैं
• अगला:=योग + 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