এই সমস্যায়, আমাদের একটি সংখ্যা 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
স্টেপ ১ - i = 1 থেকে N পর্যন্ত লুপ।
স্টেপ ১.১: if(i%2 == 0 || i%3 == 0 || i%5 == 0), count++।
স্টেপ ২ - 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
