मान लीजिए हमारे पास अंकों का एक सॉर्टेड सेट D है, जो {'1','2','3','4','5','6','7','8','9'} का एक गैर-खाली उपसमुच्चय है (0 को छोड़कर)। अब, हम इन अंकों का उपयोग करके कुछ संख्याएं लिखेंगे, प्रत्येक अंक का जितनी बार चाहें उतनी बार उपयोग कर सकते हैं। हमें उन धनात्मक पूर्णांकों की संख्या ढूंढनी है जो लिखे जा सकते हैं और N से कम या बराबर हैं।
उदाहरण के लिए, यदि D = [2,3,4,7], N = 100, तो आउटपुट 20 होगा।
हल करने का दृष्टिकोण
हम N से कम अंकों वाली संख्याओं को गिनते हैं, फिर समान अंकों वाली संख्याओं को अंक-दर-अंक गिनते हैं:
N को स्ट्रिंग में बदलें
N से कम अंकों वाली सभी संख्याओं को गिनें: sum(|D|^i)
समान अंकों की लंबाई के लिए, प्रत्येक स्थिति के लिए N के अंक से कम अंकों को गिनें
यदि N का वर्तमान अंक D में है, तो अगली स्थिति पर जारी रखें
अन्यथा, जल्दी वापस करें
यदि सभी अंक मेल खाते हैं, तो N के लिए 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;
}
};
int main(){
Solution ob;
vector<string> v = {"2","3","4","7"};
cout << (ob.atMostNGivenDigitSet(v, 100));
return 0;
}
इनपुट
{"2","3","4","7"}, 100
आउटपुट
20