এই আর্টিকেলে, আমরা 1 থেকে n (দেওয়া) পর্যন্ত যেসব সংখ্যা 2 থেকে 10 পর্যন্ত যেকোনো সংখ্যা দিয়ে ভাগীন সেগুলো বের করার সমস্যা আলোচনা করব। উদাহরণ দিয়ে বুঝি:
Input : num = 14 Output : 3 Explanation: তিনটি সংখ্যা 1, 11, এবং 13, যা ভাগীন। Input : num = 21 Output : 5 Explanation: পাঁচটি সংখ্যা 1, 11, 13, 17, এবং 19, যা ভাগীন।
সমাধানের পদ্ধতি
সহজ পদ্ধতি
যদি আমরা 1 থেকে num পর্যন্ত প্রতিটি সংখ্যা চেক করি যে কি সেটি 2 থেকে 10 পর্যন্ত যেকোনো সংখ্যা দিয়ে ভাগীন। না হলে কাউন্ট বাড়ান। কিন্তু এই পদ্ধতিতে অনেক সময় লাগবে ফলে টাইম কমপ্লেক্সিটি বাড়বে।
দক্ষ পদ্ধতি
সেরা পদ্ধতি হলো প্রথম 1 থেকে num পর্যন্ত যেসব সংখ্যা 2 থেকে 10 পর্যন্ত যেকোনো সংখ্যা দিয়ে ভাগ্যোগ্য সেগুলোর সংখ্যা বের করা, তারপর এই কাউন্টকে num দিয়ে বিয়োগ করা।
তাহলে প্রথমে আমাদের 2, 3, 4, 5, 10 দিয়ে ভাগ্যোগ্য সংখ্যা বের করতে হবে। কিন্তু 4, 6, 8, 10 দিয়ে ভাগ্যোগ্য সংখ্যা 2 দিয়ে ভাগ্যোগ্য, এবং 3 দিয়ে ভাগ্যোগ্য সংখ্যা 6 এবং 9 দিয়ে ভাগ্যোগ্য।
আমাদের 2, 3, 5, এবং 7 দিয়ে ভাগ্যোগ্য সব সংখ্যা বের করতে হবে। এবং এটি আমরা ইনক্লুশন-এক্সক্লুশন প্রিন্সিপল (inclusion-exclusion principle) দিয়ে ক্যালকুলেট করতে পারি।
ইনক্লুশন-এক্সক্লুশন প্রিন্সিপল
এটি বলে যে, আমাদের প্রতিটি সেটের আকার যোগ করতে হবে, পেয়ারওয়াইজ ইন্টারসেকশনের আকার বিয়োগ করতে হবে, তিনটি সেটের ইন্টারসেকশনের আকার যোগ করতে হবে, এবং এভাবেই চলতে থাকবে।
সকল সংখ্যা বের করার সূত্র:
= NUM – X + Y – Z + A.
যেখানে,
X = 2, 3, 5, 7 দিয়ে ভাগ্যোগ্য সংখ্যা ( [num / 2] + [num / 3] + [num / 5] + [num / 7] ) Y = (2,3), (2, 5), (2, 7), (3, 5), (3, 5), (3, 7) এবং (5, 7) দিয়ে ভাগ্যোগ্য সংখ্যা = ( [num / (2 * 3)] + [num / (2 * 5)] + [num / (2 * 7)] + [num / (3 * 5)] + num / (3 * 7)] + [num / (5 * 7)] ). Z = (2, 3, 5), (2, 3, 7), (2, 5, 7) এবং (3, 5, 7) দিয়ে ভাগ্যোগ্য সংখ্যা = ( [num / (2 * 3 * 5)] + [num / (2 * 3 * 7)] + [num / (2 * 5 * 7)] + [num / (3 * 5 * 7)] ) A = (2, 3, 5, 7) দিয়ে ভাগ্যোগ্য সংখ্যা = ( [num / (2 * 3 * 5 * 7)] )
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main() { int n = 21, result; // ইনক্লুশন-এক্সক্লুশন প্রিন্সিপল থেকে সূত্র প্রয়োগ // 2 থেকে 10 পর্যন্ত যেকোনো সংখ্যা দিয়ে ভাগ না হওয়া সংখ্যা গণনা। result = n - n / 2 - n / 3 - n / 5 - n / 7 + n / 6 + n / 10 + n / 14 + n / 15 + n / 21 + n / 35 - n / 30 - n / 42 - n / 70 - n / 105 + n / 210; cout << "The count of numbers, not div by [2, 10] is: " << result; return 0; }
আউটপুট
The count of numbers, not div by [2, 10] is: 5
উপসংহার
এই আর্টিকেলে, আমরা 2 থেকে n পর্যন্ত ভাগহীন সংখ্যা বের করার পদ্ধতি আলোচনা করেছি। এই সমস্যা সমাধানের জন্য ইনক্লুশন-এক্সক্লুশন প্রিন্সিপল আলোচনা করেছি। আমরা O(1) কমপ্লেক্সিটিতে ফলাফল পাওয়ার জন্য C++ প্রোগ্রামও আলোচনা করেছি। আপনি এই প্রোগ্রামটি Java, C, Python ইত্যাদি অন্য ভাষায়ও লিখতে পারেন। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
