इस समस्या में, हमें एक संख्या N दी जाती है। हमारा कार्य 2 या 3 या 5 N से कम या उसके बराबर के गुणज ज्ञात करना है।
समस्या का विवरण - हम 1 से N तक के सभी तत्वों की गणना करेंगे जो 2 या 3 या 5 से विभाज्य हैं।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
N = 7
आउटपुट
5
स्पष्टीकरण
All the elements from 1 to 7 are : 1, 2, 3, 4, 5, 6, 7. Elements divisible by 2/3/5 are 2, 3, 4, 5, 6
समाधान दृष्टिकोण
समस्या को हल करने का एक आसान तरीका यह है कि 1 से N तक की सभी संख्याओं को ट्रेस किया जाए और 2 या 3 या 5 से विभाजित होने वाली सभी संख्याओं को गिनें।
एल्गोरिदम
आरंभ करें - गिनती =0
चरण 1 - i =1 से N के लिए लूप।
चरण 1.1 :अगर (i%2 ==0 || i%3 ==0 || i%5 ==0), गिनती++।
चरण 2 - वापसी की संख्या।
एक और तरीका
समस्या को हल करने का एक अधिक प्रभावी तरीका सेट थ्योरी का उपयोग करना है।
2 से विभाज्य संख्या की संख्या n(2) है
3 से विभाज्य संख्या की संख्या है n(3)
5 से विभाज्य संख्या की संख्या है n(5)
2 और 3 से विभाज्य संख्या की संख्या n(2 n 3)
. है2 और 5 से विभाज्य संख्या की संख्या n(2 n 5)
. है3 और 5 से विभाज्य संख्या की संख्या n(3 n 5)
. है2 और 3 और 5 से विभाज्य संख्या की संख्या n(2 n 3 n 5)
. है2 या 3 या 5 से विभाज्य संख्या की संख्या n(2 U 3 U 5)
. हैसेट सिद्धांत पर आधारित,
एन (2 ∪ 3 ∪ 5) =एन (2) + एन (3) + एन (5) - एन (2 ∩ 3) - एन (2 ∩ 5) - एन (3 ∩ 5) + एन (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