इस समस्या में, हमें एक संख्या N दी जाती है। हमारा कार्य N से कम या बराबर 2 या 3 या 5 के गुणज ढूंढना है।
समस्या विवरण – हम 1 से N तक के उन सभी तत्वों को गिनेंगे जो 2 या 3 या 5 से विभाज्य हैं।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
N = 7
आउटपुट
5
व्याख्या
1 से 7 तक के सभी तत्व हैं : 1, 2, 3, 4, 5, 6, 7. 2/3/5 से विभाज्य तत्व हैं 2, 3, 4, 5, 6
समाधान दृष्टिकोण
समस्या को हल करने का एक सरल दृष्टिकोण 1 से N तक सभी संख्याओं को पार करना और उन सभी संख्याओं को गिनना है जो 2 या 3 या 5 से विभाजित होती हैं।
एल्गोरिदम
आरंभ करें – count = 0
चरण 1 – i = 1 से N तक लूप।
चरण 1.1: if(i%2 == 0 || i%3 == 0 || i%5 == 0), count++।
चरण 2 – count वापस करें।
एक अन्य दृष्टिकोण
समस्या को हल करने का एक अधिक प्रभावी दृष्टिकोण सेट सिद्धांत का उपयोग करना है।
2 से विभाज्य संख्याओं की गिनती n(2) है
3 से विभाज्य संख्याओं की गिनती n(3) है
5 से विभाज्य संख्याओं की गिनती n(5) है
2 और 3 से विभाज्य संख्याओं की गिनती n(2 ∩ 3) है
2 और 5 से विभाज्य संख्याओं की गिनती n(2 ∩ 5) है
3 और 5 से विभाज्य संख्याओं की गिनती n(3 ∩ 5) है
2 और 3 और 5 से विभाज्य संख्याओं की गिनती n(2 ∩ 3 ∩ 5) है
2 या 3 या 5 से विभाज्य संख्याओं की गिनती n(2 ∪ 3 ∪ 5) है
सेट सिद्धांत के आधार पर,
n(2 ∪ 3 ∪ 5) = n(2) + n(3) + n(5) - n(2 ∩ 3) - n(2 ∩ 5) - n(3 ∩ 5) + n(2 ∩ 3 ∩ 5)
समाधान संख्याओं के बिट मास्क की गणना करके पाया जाता है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <bits/stdc++.h> using namespace std; int countMultiples(int n) { int values[] = { 2, 3, 5 }; int countMultiples = 0, bitMask = pow(2, 3); for (int i = 1; i < bitMask; i++) { int prod = 1; for (int j = 0; j < 3; j++) { if (i & 1 << j) prod = prod * values[j]; } if (__builtin_popcount(i) % 2 == 1) countMultiples = countMultiples + n / prod; else countMultiples = countMultiples - n / prod; } return countMultiples; } int main() { int n = 13; cout<<"The number of multiples till "<<n<<" is "<<countMultiples(n)<<endl; return 0; }आउटपुट
The number of multiples till 13 is 9