C++ में a या b से विभाज्य Nवां पद ढूंढना

इस समस्या में, हमें तीन संख्याएं A, B, और N दी गई हैं। हमारा कार्य C++ में A या B से विभाज्य Nवां पद ढूंढने के लिए एक प्रोग्राम बनाना है।

समस्या विवरण

A या B से विभाज्य Nवां पद। यहां, हम उस nवीं संख्या को ढूंढेंगे जो संख्या A या B से विभाज्य है। इसके लिए, हम A या B से विभाज्य संख्याओं को nth संख्या तक गिनेंगे।

उदाहरण

इनपुट A = 4, B = 3, N = 5

आउटपुट 9

व्याख्या

वे पद जो 3 और 4 से विभाज्य हैं:

3, 4, 6, 8, 9, 12, ...

5वां पद 9 है।

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

A या B से विभाज्य nवां पद ढूंढने के लिए। हम बस A या B से विभाज्य संख्याएं ढूंढ सकते हैं और श्रृंखला में nवां पद हमारा उत्तर है।

उदाहरण

#include <iostream> 
using namespace std; 

int findNTerm(int N, int A, int B) { 
    int count = 0; 
    int num = 1; 
    while(count < N){ 
        if(num % A == 0 || num % B == 0) 
            count++; 
        if(count == N) 
            return num; 
        num++; 
    } 
    return 0; 
} 

int main(){ 
    int N = 12, A = 3, B = 4; 
    cout << N << "th term divisible by " << A << " or " << B << " is " << findNTerm(N, A, B) << endl; 
}

आउटपुट

12th term divisible by 3 or 4 is 24

समस्या को हल करने का एक अन्य दृष्टिकोण Nth तत्व को ढूंढने के लिए बाइनरी सर्च का उपयोग करना हो सकता है जो A या B से विभाज्य है। हम सूत्र का उपयोग करके Nth पद ढूंढेंगे:

NTerm = maxNum/A + maxNum/B + maxNum/lcm(A,B)

और Nterm के मान के आधार पर, हम जांचेंगे कि क्या हमें maxNum से कम संख्याओं में या maxNum से अधिक संख्याओं में पार करने की आवश्यकता है।

उदाहरण

#include <iostream> 
using namespace std; 

int findLCM(int a, int b) { 
    int LCM = a, i = 2; 
    while(LCM % b != 0) { 
        LCM = a*i; 
        i++; 
    } 
    return LCM; 
} 

int findNTerm(int N, int A, int B) { 
    int start = 1, end = (N*A*B), mid; 
    int LCM = findLCM(A, B); 
    while (start < end) { 
        mid = start + (end - start) / 2; 
        if (((mid/A) + (mid/B) - (mid/LCM)) < N) 
            start = mid + 1; 
        else 
            end = mid; 
    } 
    return start; 
} 

int main() { 
    int N = 12, A = 3, B = 4; 
    cout << N << "th term divisible by " << A << " or " << B << " is " << findNTerm(N, A, B); 
}

आउटपुट

12th term divisible by 3 or 4 is 24