मान लीजिए कि हमारे पास एक धनात्मक पूर्णांक N है, हमें N से कम या उसके बराबर धनात्मक पूर्णांकों की संख्या ज्ञात करनी है, जिनमें कम से कम 1 दोहराए गए अंक हैं।
इसलिए, यदि इनपुट 99 की तरह है, तो आउटपुट 9 होगा, क्योंकि हमारे पास 11, 22, 33, 44, 55, 66, 77, 88, 99 जैसे नंबर हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
फ़ंक्शन A() को परिभाषित करें, इसमें m, n,
. लगेगा-
रिट :=1
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
रिट:=रिट * मी
-
(मी को 1 से घटाएं)
-
-
वापसी रिट
-
-
मुख्य विधि से निम्न कार्य करें -
-
एक सरणी गिरफ्तारी परिभाषित करें
-
प्रारंभ करने के लिए i :=N + 1, जब i> 0, अद्यतन i :=i / 10, करें -
-
एआर के पहले तत्व को इंडेक्स आई मॉड 10 में एआर में डालें
-
-
रिट:=0
-
n :=गिरफ्तारी का आकार
-
इनिशियलाइज़ करने के लिए मैं :=1, जब i
-
रिट :=रिट + 9 * ए(9, आई - 1)
-
-
देखे गए एक सेट को परिभाषित करें
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
अंक:=गिरफ्तारी [i]
-
प्रारंभ करने के लिए j :=(यदि i 0 के समान है, तो 1, अन्यथा 0), जब j <अंक, अद्यतन (1 से j बढ़ाएँ), करें -
-
अगर j का दौरा किया जाता है, तो -
-
निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं
-
-
रिट :=रिट + ए(9 - i, n - i - 1)
-
-
अगर डिजिट विजिट किया गया है, तो -
-
लूप से बाहर आएं
-
-
विज़िट किए गए में अंक डालें
-
-
वापसी एन - रिट
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int A(int m, int n){
int ret = 1;
for (int i = 0; i < n; i++) {
ret *= m;
m--;
}
return ret;
}
int numDupDigitsAtMostN(int N){
vector<int> arr;
for (int i = N + 1; i > 0; i /= 10) {
arr.insert(arr.begin(), i % 10);
}
int ret = 0;
int n = arr.size();
for (int i = 1; i < n; i++) {
ret += 9 * A(9, i - 1);
}
set<int> visited;
for (int i = 0; i < n; i++) {
int digit = arr[i];
for (int j = i == 0 ? 1 : 0; j < digit; j++) {
if (visited.count(j))
continue;
ret += A(9 - i, n - i - 1);
}
if (visited.count(digit))
break;
visited.insert(digit);
}
return N - ret;
}
};
main(){
Solution ob;
cout << (ob.numDupDigitsAtMostN(99));
} इनपुट
99
आउटपुट
9