C++ में केवल अभाज्य अंकों (2, 3, 5, 7) से बनी Nवीं संख्या खोजना

समस्या विवरण

इस समस्या में, हमें एक संख्या N दी गई है। हमारा कार्य केवल अभाज्य अंकों (2, 3, 5 और 7) से बनी Nवीं संख्या खोजना है।

केवल अभाज्य अंकों (2, 3, 5, 7) से बनी श्रृंखला है: 2, 3, 5, 7, 22, 23, 25, 27, 32, 33...

उदाहरण

इनपुट: N = 6
आउटपुट: 23

हल का दृष्टिकोण

समस्या को हल करने का एक सरल दृष्टिकोण दिए गए इंडेक्स पर संख्या खोजना है यानी श्रृंखला का पद खोजना, इसके लिए हम श्रृंखला का अवलोकन करेंगे।

हमारे पास चार अलग-अलग अभाज्य संख्याएं हैं इसलिए बनी श्रृंखला को चार-अंकीय संख्या प्रणाली के रूप में माना जा सकता है। इस संख्या प्रणाली में, हमारे पास लंबाई x की 4ˣ संख्याएं हैं।

अब समस्या को हल करने के लिए, हमारे पास वह श्रृंखला है जिसमें हम उन संख्याओं की लंबाई खोजेंगे जो उन्हें संख्या बनाने में मदद करती हैं। फिर हम Nवीं संख्या गिनेंगे और आवश्यक संख्या प्रिंट करेंगे।

लंबाई का उपयोग करके Nवीं संख्या खोजने के लिए, हम लंबाई (x-1) की पहली संख्या से गिनती करेंगे और फिर इस N को गिनेंगे।

C++ कार्यान्वयन

#include <iostream> 
#include <cmath> 
using namespace std; 

void findNthNumber(int n) {
    long x = 1;
    long lastNum = 0;
    
    // लंबाई x खोजें जैसे कि लंबाई ≤ x की संख्याओं की संख्या ≥ n हो
    while (true) {
        long currNum = lastNum + pow(4, x);
        if (lastNum < n && currNum >= n)
            break;
        x++;
        lastNum = currNum;
    }
    
    // अब x अंकों की संख्या बनाएं
    for (int i = 1; i <= x; i++) {
        for (long j = 1; j <= 4; j++) {
            if (lastNum + pow(4, x - i) < n) {
                lastNum += pow(4, x - i);
            } else {
                if (j == 1) cout << "2";
                else if (j == 2) cout << "3";
                else if (j == 3) cout << "5";
                else if (j == 4) cout << "7";
                break;
            }
        }
    }
}

int main() {
    int N = 32;
    cout << N << "वीं केवल अभाज्य अंकों से बनी संख्या है ";
    findNthNumber(N);
    return 0;
}

आउटपुट

32वीं केवल अभाज्य अंकों से बनी संख्या है 257

पैटर्न समझ

जटिलता विश्लेषण

• समय जटिलता: O(log₄ N) ≈ O(log N)
• स्पेस जटिलता: O(1)

मुख्य अंतर्दृष्टि

यह आधार-4 संख्या प्रणाली में परिवर्तित करने के समान है जहां अंक 0,1,2,3 को 2,3,5,7 पर मैप किया जाता है।