এই আর্টিকেলে আমরা ওই কোয়াড্রুপলেট (চারটি সংখ্যা) সংখ্যা বের করার সকল সম্ভাব্য পদ্ধতি বর্ণনা করব যেখানে প্রথম ৩টি পদ অंकগণিতিকسلسل (A.P.)-এ এবং শেষ ৩টি পদ জ্যামিতিকسلسل (G.P.)-এ থাকে। প্রথমে আমরা A.P. এবং G.P.-এর মৌলিক সংজ্ঞা ব্যাখ্যা করব।
অঙ্কগণিতিকسلسل (A.P.) − এটি একটি সংখ্যা সিকোয়েন্স যেখানে কমন ডিফারেন্স (d) একই বা কনস্ট্যান্ট থাকে অর্থাৎ দুটি последователь সংখ্যার পার্থক্য কনস্ট্যান্ট। উদাহরণ: 1,3,5,7,9 | d = 2
জ্যামিতিকسلسل (G.P.) − এটি একটি সংখ্যা সিকোয়েন্স যেখানে কমন রেশিও (r) একই থাকে অর্থাৎ প্রতিটি পদ পূর্ববর্তী সংখ্যাকে একটি নির্দিষ্ট সংখ্যা দিয়ে গুণ করে পাওয়া যায়। উদাহরণ: 3, 6, 12, 24,.... | r = 2
এই সমস্যায় আমাদের বের করতে হবে একটি অ্যারে arr[ ]-এ N পূর্ণসংখ্যা থেকে কতগুলো ইনডেক্স কোয়াড্রুপলেট (a, b, c, d) আছে। ফলে arr[a], arr[b], arr[c] A.P.-এ থাকবে, এবং arr[d], arr[c], arr[b] G.P.-এ থাকবে যেখানে সব কোয়াড্রুপলেট ডিফিনিট হবে। উদাহরণ:
ইনপুট : arr[ ] = { 9, 6, 4, 2, 1, 2 }
আউটপুট : 2
ব্যাখ্যা: কোয়াড্রুপলেটের এলিমেন্টগুলো { 3, 2, 1, 0 } এবং { 5, 2, 1, 0 } ইনডেক্সে যেখানে কোয়াড্রুপলেট { 2, 4, 6, 9 } উভয় পজিশনে।
ইনপুট : arr[ ] = { 2, 6, 1, 4, 2 }
আউটপুট : 2
ব্যাখ্যা: কোয়াড্রুপলেটের এলিমেন্টগুলো { 1, 3, 0, 2 } এবং { 1, 3, 4, 2 } ইনডেক্সে যেখানে কোয়াড্রুপলেট { 6, 4, 2, 1 } উভয় পজিশনে।
সমাধানের পদ্ধতি
এখন আমরা সমাধান বের করার দুটি ভিন্ন পদ্ধতি বর্ণনা করব:
ব্রুট ফোর্স পদ্ধতি
এটি চারটি নেস্টেড লুপ ব্যবহার করে এই সমস্যা সমাধানের সহজ পদ্ধতি, তারপর চেক করা হয় প্রথম তিনটি এলিমেন্ট A.P.-এ আছে কিনা। হ্যাঁ হলে চেক করা হয় শেষ ৩টি এলিমেন্ট G.P.-এ আছে কিনা। হ্যাঁ হলে কাউন্ট ভেরিয়েবল ১ বাড়ানো হয়। তবে এই পদ্ধতি সময় সাপেক্ষ কারণ এর সময় জটিলতা O(n⁴)।
দক্ষ পদ্ধতি (Efficient Approach)
এই পদ্ধতিতে আমরা প্রথমে প্রতিটি অ্যারে এলিমেন্টের কাউন্ট বের করি, তারপর দ্বিতীয় এবং তৃতীয় এলিমেন্ট ধরে দুইটি নেস্টেড লুপ চালাই, তখন প্রথম এলিমেন্ট হবে arr[b] – (arr[c] – arr[b]) এবং চতুর্থ এলিমেন্ট হবে arr[c] * arr[c] / arr[b]।
উদাহরণ
#include <bits/stdc++.h> using namespace std; int main (){ unordered_map < int, int > map; int arr[] = { 2, 6, 1, 4, 2 }; int size = sizeof (arr) / sizeof (arr[0]); // প্রতিটি এলিমেন্ট প্রসেস করে কাউন্ট বাড়ানো for (int a = 0; a < size; a++) map[arr[a]]++; int count = 0; // দ্বিতীয় ও তৃতীয় এলিমেন্টের জন্য দুইটি নেস্টেড লুপ for (int b = 0; b < size; b++){ for (int c = 0; c < size; c++){ if (b == c) continue; // কাউন্ট কমানো map[arr[b]]--; map[arr[c]]--; // কমন ডিফারেন্স ব্যবহার করে প্রথম এলিমেন্ট বের করা int first = arr[b] - (arr[c] - arr[b]); // GP ব্যবহার করে চতুর্থ এলিমেন্ট বের করা int fourth = (arr[c] * arr[c]) / arr[b]; if ((arr[c] * arr[c]) % arr[b] == 0){ // बरাবর না হলে কাউন্ট বাড়াও if (arr[b] != arr[c]) count += map[first] * map[fourth]; else count += map[first] * (map[fourth] - 1); } map[arr[b]]++; map[arr[c]]++; } } cout <<"Number of quadruples: " << count; return 0; }
আউটপুট
Number of quadruples: 2
উপরোক্ত কোডের ব্যাখ্যা
এই কোডে আমরা কম্বিনেটরিক্স ব্যবহার করি এবং দ্বিতীয় ও তৃতীয় এলিমেন্টের জন্য দুইটি নেস্টেড লুপ চালিয়ে প্রথম এলিমেন্ট arr[a] – (arr[c] – arr[b]) এবং চতুর্থ এলিমেন্ট arr[c] * arr[c] / arr[b] দিয়ে বের করি। তাই A এবং B ইনডেক্স দ্বারা কোয়াড্রুপলেট সংখ্যা হবে প্রথম সংখ্যা * চতুর্থ সংখ্যা, দ্বিতীয় ও তৃতীয় এলিমেন্ট ফিক্স রেখে। এখানে উপরের কোডের সময় জটিলতা O(n²)।
উপসংহার
এই আর্টিকেলে আমরা সমাধান করেছি যেখানে প্রথম তিনটি পদ AP-এ এবং শেষ তিনটি পদ GP-এ থাকে এমন কোয়াড্রুপলেট সংখ্যা বের করা, এবং দুটি পদ্ধতি আলোচনা করেছি ব্রুটফোর্স [O(n⁴)] এবং দক্ষ পদ্ধতি [O(n²)]।
আমরা এই সমস্যাটি C++-এ সমাধান করেছি, এবং এটি Java, Python, C বা অন্য প্রোগ্রামিং ভাষায়ও সমাধান করা যায়।
