C++ में उन प्राकृतिक संख्याओं की गिनती जिनके सभी क्रमपरिवर्तन (permutations) उस संख्या से बड़े या बराबर हैं

समस्या विवरण

हमें एक प्राकृतिक संख्या num दी गई है। उन सभी प्राकृतिक संख्याओं की गिनती करनी है जिनके सभी संभावित क्रमपरिवर्तन (permutations) दिए गए संख्या num से बड़े या बराबर हैं।

शर्तें

• केवल प्राकृतिक संख्याएं मान्य हैं।
• संख्या के सभी संभावित क्रमपरिवर्तन दिए गए संख्या से बड़े या बराबर होने चाहिए।

उदाहरण

इनपुट: num = 10

आउटपुट: 9

व्याख्या: 1 से 9 तक की संख्याओं के क्रमपरिवर्तन स्वयं के बराबर होते हैं।

इनपुट: num = 13

आउटपुट: 12

व्याख्या: 1-9, 11, 12 (21>13), 13 (31>13) मान्य हैं।

समाधान दृष्टिकोण

1. अधिकतम आकार 9 सेट करें (कम से कम 9 एक-अंकीय संख्याएं हमेशा मान्य होती हैं)।
2. 1 से 9 तक लूप चलाएं, प्रत्येक को सूची में जोड़ें यदि ≤ num।
3. सूची के अंत से शुरुआत तक पार करें, प्रत्येक तत्व के लिए अगला अंक (अंतिम अंक से 9 तक) जोड़कर नई संख्या बनाएं।
4. यदि नई संख्या ≤ num, तो सूची के सामने जोड़ें और गिनती बढ़ाएं।

कार्यकारी प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

void countValidNumbers(int num) {
    int count = 0;
    int max_size = 9;
    for (int i = 1; i <= max_size; i++) {
        list<int> lists;
        if (i <= num) {
            lists.push_back(i);
            count++;
        }
        for (auto iter = lists.end(); iter != lists.begin(); ) {
            --iter;
            int first_ele = *iter;
            lists.erase(iter);
            for (int next = first_ele % 10; next <= 9; next++) {
                int temp = first_ele * 10 + next;
                if (temp <= num) {
                    lists.push_front(temp);
                    count++;
                }
            }
        }
    }
    cout << "num " << num << " के लिए गिनती: " << count << endl;
}

int main() {
    countValidNumbers(1);
    countValidNumbers(9);
    countValidNumbers(7);
    countValidNumbers(0);
    countValidNumbers(12);
    return 0;
}

आउटपुट

num 1 के लिए गिनती: 1
num 9 के लिए गिनती: 9
num 7 के लिए गिनती: 7
num 0 के लिए गिनती: 0
num 12 के लिए गिनती: 11