मान लीजिए हमारे पास एक धनात्मक पूर्णांक N है, हमें N से कम या बराबर उन धनात्मक पूर्णांकों की संख्या ढूंढनी है जिनमें कम से कम 1 दोहराया गया अंक है।
उदाहरण के लिए, यदि इनपुट 99 है, तो आउटपुट 9 होगा, क्योंकि हमारे पास 11, 22, 33, 44, 55, 66, 77, 88, 99 जैसी संख्याएं हैं।
हल करने का दृष्टिकोण
हम पूरक गिनती का उपयोग करते हैं: N से कम या बराबर उन संख्याओं को गिनें जिनके सभी अंक अलग-अलग हैं, फिर N से घटाएं।
संयोजन A(m, n) = m * (m-1) * ... * (m-n+1) की गणना करने के लिए फ़ंक्शन A(m, n) परिभाषित करें
N+1 को अंक सरणी में बदलें
N से कम अंकों वाली सभी-अलग-अलग-अंकों वाली संख्याओं को गिनें
समान अंकों की लंबाई वाली संख्याओं के लिए, अंक-दर-अंक डीपी के साथ गिनें
पहले से उपयोग किए गए अंकों को ट्रैक करने के लिए विज़िटेड सेट का उपयोग करें
अंत में N - (सभी-अलग-अलग-अंकों की गिनती) लौटाएं
उदाहरण
#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();
// N से कम अंकों वाली संख्याएं
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;
}
};
int main(){
Solution ob;
cout << (ob.numDupDigitsAtMostN(99));
return 0;
}
इनपुट
99
आउटपुट
9