C++ में अधिकतम N दिए गए अंक सेट पर संख्याएं

मान लीजिए कि हमारे पास अंकों D का एक क्रमबद्ध सेट है, जो {'1', '2', '3', '4', '5', '6', '7', '8', ' का एक गैर-रिक्त उपसमुच्चय है। 9'} 0 को छोड़कर। अब, हम इन अंकों का उपयोग करके कुछ संख्याएँ लिखेंगे, प्रत्येक अंक का जितनी बार चाहें उतनी बार उपयोग करेंगे। इसलिए, यदि D ={'2','3','7'}, तो हम '23', '771', '2372327' जैसी संख्याएँ लिख सकते हैं।

अब हमें उन धनात्मक पूर्णांकों की संख्या ज्ञात करनी है जो N से कम या उसके बराबर लिखे जा सकते हैं।

इसलिए, यदि इनपुट डी =[2,3,4,7], एन =100 जैसा है, तो आउटपुट 20 होगा, क्योंकि संख्याएं 2, 3, 4, 7, 22, 23, 24, 27 हो सकती हैं। , 32, 33, 34, 37, 42, 43, 44, 47, 72, 73, 74, 77. अन्य सभी संख्याएँ 100 से बड़ी हैं।

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

• n :=N को स्ट्रिंग में बदलें

• sz :=n का आकार, ret :=0

• इनिशियलाइज़ i :=1 के लिए, जब i

  • रिट:=रिट + (डी का आकार)^i

• इनिशियलाइज़ i :=0 के लिए, जब i

  • hasSameNum :=false

  • डी में प्रत्येक स्ट्रिंग x के लिए -

    • अगर x[0]

      • ret :=ret + (D का आकार)^(sz - i - 1)

    • अन्यथा जब x[0], n[i] के समान हो, तब -

      • hasSameNum :=true

  • यदि नहीं hasSameNum गैर-शून्य है, तो -

    • वापसी रिट

• रिटर्न रिट + 1

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int atMostNGivenDigitSet(vector<string> &D, int N) {
      string n = to_string(N);
      int sz = n.size();
      int ret = 0;
      for (int i = 1; i < sz; i++) {
         ret += pow(D.size(), i);
      }
      for (int i = 0; i < sz; i++) {
         bool hasSameNum = false;
         for (string &x : D) {
            if (x[0] < n[i]) {
               ret += pow(D.size(), sz - i - 1);
            } else if (x[0] == n[i]) {
               hasSameNum = true;
            }
         }
         if (!hasSameNum)
         return ret;
      }
      return ret + 1;
   }
};
main(){
   Solution ob;
   vector<string> v = {"2","3","4","7",};
   cout << (ob.atMostNGivenDigitSet(v, 100));
}

इनपुट

{"2","3","4","7"}, 100

आउटपुट

20