এই আর্টিকেলে, আমাদের একটি সমস্যা দেওয়া আছে: একটি অ্যারে দেওয়া আছে এবং দুটি টাইপের কোয়েরি আছে जिनका উত্তর দিতে হবে।
- টাইপ ০ − x (দেওয়া মান) চেয়ে বড় বা সমান উপাদানগুলোর সংখ্যা বের করতে হবে।
- টাইপ ১ − x (দেওয়া মান) চেয়ে স্ট্রিক্টলি বড় উপাদানগুলোর সংখ্যা বের করতে হবে।
একটি সহজ উদাহরণ:
Input : arr[] = { 10, 15, 30 , 40, 45 } and Q = 3 Query 1: 0 50 Query 2: 1 40 Query 3: 0 30 Output : 0 1 3 Explanation: x = 50, q = 0 : 50 চেয়ে বড় বা সমান কোনো উপাদান নেই। x = 40, q = 1 : 45, 40 চেয়ে বড়। x = 30, q = 0 : তিনটি উপাদান 30, 40, 45, 30 চেয়ে বড় বা সমান।
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের জন্য দুটি ভিন্ন পদ্ধতি ব্যবহার করা যায়। প্রথমে ব্রুট ফোর্স সমাধান ব্যবহার করব, তারপর দেখব এটি উচ্চ কনস্ট্রেইন্টের জন্য কাজ করে কিনা। না হলে অপ্টিমাইজ করব।
ব্রুট ফোর্স পদ্ধতি
এই পদ্ধতিতে, আমরা সব q কোয়েরির জন্য অ্যারেটি ট্রাভার্স করব এবং শর্ত পূরণকারী সংখ্যাগুলো খুঁজে বের করব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; void query(int *arr, int n, int type, int val) { int count = 0; // উত্তর if(!type) { // টাইপ ০ কোয়েরি হলে for(int i = 0; i < n; i++) { if(arr[i] >= val) count++; } } else { // টাইপ ১ কোয়েরি হলে for(int i = 0; i < n; i++) { if(arr[i] > val) count++; } } cout << count << "\n"; } int main() { int ARR[] = { 10, 15, 30, 40, 45 }; int n = sizeof(ARR)/sizeof(ARR[0]); // অ্যারের আকার query(ARR, n, 0, 50); // কোয়েরি ১ query(ARR, n, 1, 40); // কোয়েরি ২ query(ARR, n, 0, 30); // কোয়েরি ৩ return 0; }
আউটপুট
0 1 3
উপরের পদ্ধতিতে, আমরা সিম্পলি অ্যারেটি ট্রাভার্স করে কোয়েরির উত্তর বের করছি। এটি দেওয়া উদাহরণের জন্য কাজ করে, কিন্তু উচ্চ কনস্ট্রেইন্টে ফেল করবে কারণ ওভারঅল টাইম কমপ্লেক্সিটি O(N*Q), যেখানে N হল অ্যারের আকার এবং Q হল কোয়েরি সংখ্যা। তাই আমরা এই পদ্ধতিকে অপ্টিমাইজ করব যাতে এটি উচ্চ কনস্ট্রেইন্টেও কাজ করে।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা বাইনারি সার্চ ব্যবহার করে দেওয়া মানটির আপার বাউন্ড (upper bound) এবং লোয়ার বাউন্ড (lower bound) খুঁজে বের করব। প্রথমে আমরা আমাদের অ্যারেটিকে সর্ট করব বাইনারি সার্চের জন্য, তারপর লোয়ার বাউন্ড এবং আপার বাউন্ড ফাংশন প্রয়োগ করব।
উদাহরণ
#include <bits/stdc++.h> using namespace std; void lowerbound(int *arr, int n, int val) { int l = -1, r = n; while(r - l > 1) { // বাইনারি সার্চ করে উত্তর খুঁজুন int mid = (l+r)/2; if(arr[mid] >= val) r = mid; else l = mid; } if(r == n) // r যদি অচল থাকে তবে শর্ত পূরণকারী কোনো উপাদান নেই cout << "0\n"; else cout << n - r << "\n"; } void upperbound(int *arr, int n, int val) { int l = -1, r = n; while(r - l > 1) { // বাইনারি সার্চ করে উত্তর খুঁজুন int mid = (l+r)/2; if(arr[mid] > val) r = mid; else l = mid; } if(r == n)// r যদি অচল থাকে তবে শর্ত পূরণকারী কোনো উপাদান নেই cout << "0\n"; else cout << n - r <<"\n"; } void query(int *arr, int n, int type, int val) { if(!type) // টাইপ == ০ হলে লোয়ার বাউন্ড ফাংশন কল lowerbound(arr, n, val); else // টাইপ == ১ হলে আপার বাউন্ড ফাংশন কল upperbound(arr, n, val); } int main() { int arr[] = { 1, 2, 3, 4 }; int n = sizeof(arr)/sizeof(arr[0]); // অ্যারের আকার sort(arr, arr+n); // অ্যারে সর্ট করুন query(arr, n, 0, 5); // কোয়েরি ১ query(arr, n, 1, 3); // কোয়েরি ২ query(arr, n, 0, 3); // কোয়েরি ৩ return 0; }
আউটপুট
0 1 2
উপরের কোড বাইনারি সার্চে কাজ করে যা আমাদের টাইম কমপ্লেক্সিটি 크게 কমিয়ে দেয়। সুতরাং আমাদের চূড়ান্ত কমপ্লেক্সিটি হয় O(NlogN), যেখানে N হল অ্যারের আকার।
উপরোক্ত কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা বাইনারি সার্চ ব্যবহার করে দেওয়া মানটির আপার বাউন্ড এবং লোয়ার বাউন্ড খুঁজে বের করব। বাইনারি সার্চের জন্য আমরা প্রথমে আমাদের অ্যারেটিকে সর্ট করি কারণ এটি শুধু সর্ট করা অ্যারেতে কাজ করে। আমরা আমাদের লোয়ার বাউন্ড এবং আপার বাউন্ড ফাংশন তৈরি করি যা যথাক্রমে টাইপ ০ এবং টাইপ ১ শর্ত পূরণকারী প্রথম সংখ্যা খুঁজে বের করতে সাহায্য করে। এখন যেহেতু আমরা অ্যারেটিকে সর্ট করেছি, শর্ত পূরণকারী প্রথম সংখ্যা পাওয়া যাওয়ার পর, এই উপাদানের পরে থাকা সব উপাদানও শর্ত পূরণ করবে। তাই আমরা এই উপাদানের সূচক এবং N (অ্যারের আকার) এর পার্থক্য প্রিন্ট করি।
উপসংহার
এই আর্টিকেলে, আমরা বাইনারি সার্চ ব্যবহার করে "আরও বড়" এবং "কম নয়" টাইপের কোয়েরি সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ ও দক্ষ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
