इस समस्या में, हमें तीन नंबर A, B और N दिए गए हैं। हमारा काम C++ में A या B से विभाज्य Nवें पद को खोजने के लिए एक प्रोग्राम बनाना है।
समस्या का विवरण
A या B से विभाज्य Nवाँ पद। यहाँ, हम n संख्या पद पाएंगे जो संख्या A या B से विभाज्य है। इसके लिए, हम nth संख्याओं तक गिनेंगे जो A या B से विभाज्य हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
ए =4, बी =3, एन =5
आउटपुट
9
स्पष्टीकरण
3 और 4 से विभाज्य पद हैं -
3, 4, 6, 8, 9, 12, …
5वाँ पद 9 है।
समाधान दृष्टिकोण
nवाँ पद ज्ञात करना जो A या B से विभाज्य हो। हम केवल 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