এই প্রবন্ধে, আমরা চতুর্গুণের সংখ্যা খুঁজে বের করার জন্য প্রতিটি সম্ভাব্য পদ্ধতির বর্ণনা করব যেখানে প্রথম 3টি পদ A.P. এ আছে এবং শেষ 3টি 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
এই সমস্যায়, N পূর্ণসংখ্যার একটি অ্যারে [ ] থেকে আমাদের নির্ধারণ করতে হবে কতগুলি সূচক চতুর্গুণ (a, b, c, d) আছে। ফলস্বরূপ, arr[a], arr[b], এবং arr[c] A.P. তে আছে, এবং arr[d], arr[c] এবং arr[b] G.P তে আছে। যেখানে সমস্ত চতুর্গুণ নির্দিষ্ট হওয়া উচিত। সুতরাং এখানে উদাহরণ -
Input : arr[ ] = { 9, 6, 4, 2, 1, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 3, 2, 1, 0 } and { 5, 2, 1, 0 } indexes where quadruples are { 2, 4, 6, 9 } for both positions.
Input : arr[ ] = { 2, 6, 1, 4, 2 }
Output : 2
Explanation: Elements in the quadruples are at { 1, 3, 0, 2 } and { 1, 3, 4, 2 } indexes where quadruples are { 6, 4, 2, 1 } for both positions. সমাধান খোঁজার পদ্ধতি
এখন, আমরা সমাধান খুঁজতে দুটি ভিন্ন পন্থা বর্ণনা করব −
ব্রুট ফোর্স অ্যাপ্রোচ
চারটি নেস্টেড লুপ ব্যবহার করে এই সমস্যাটি সমাধান করার জন্য এটি একটি সহজ পদ্ধতি, তারপর প্রথম তিনটি উপাদান A.P-এ আছে কিনা তা পরীক্ষা করুন৷ যদি হ্যাঁ, তাহলে শেষ 3টি উপাদান G.P-এ আছে কি না তা পরীক্ষা করুন৷ যদি হ্যাঁ, তাহলে কাউন্ট ভেরিয়েবলকে 1 দ্বারা বৃদ্ধি করুন। যাইহোক, এই পদ্ধতিটি সময়সাপেক্ষ কারণ এর সময়ের জটিলতা হল O(n4) .
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা প্রথমে প্রতিটি অ্যারের উপাদানের গণনা খুঁজে পাই, তারপর উভয় উপাদানকে দ্বিতীয় এবং তৃতীয় সংখ্যা হিসাবে বিবেচনা করি এবং দুটি নেস্টেড লুপ চালাই, তারপর প্রথম উপাদানটি হবে 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]);
// Processing every elent and increasing the count
for (int a = 0; a < size; a++)
map[arr[a]]++;
int count = 0;
// Running two nested loops for second & third element
for (int b = 0; b < size; b++){
for (int c = 0; c < size; c++){
if (b == c)
continue;
// Decreasing the count
map[arr[b]]--;
map[arr[c]]--;
// Finding the first element using common difference
int first = arr[b] - (arr[c] - arr[b]);
// Finding the fourth element using GP
int fourth = (arr[c] * arr[c]) / arr[b];
if ((arr[c] * arr[c]) % arr[b] == 0){
// Increment count if not equal
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(n2) .
উপসংহার
এই নিবন্ধে, আমরা চতুর্গুণের সংখ্যা খুঁজে বের করার সমস্যাটি সমাধান করি যেখানে প্রথম তিনটি পদ AP-তে রয়েছে এবং শেষ তিনটি পদ GP-তে রয়েছে, এবং আমরা Bruteforce[O(n4)] এবং Efficient ব্যবহার করে এটি সমাধান করার দুটি পন্থা নিয়ে আলোচনা করেছি। পন্থা [ O(n2)]।
আমরা C++ ব্যবহার করে এই সমস্যার সমাধান করেছি, এবং এটি জাভা, পাইথন, সি বা অন্য কোনো প্রোগ্রামিং ভাষার মতো বিভিন্ন ভাষায় এই সমস্যার সমাধান করতে পারে।
