এই নিবন্ধে, আমাদের একটি সমস্যা দেওয়া হয়েছে, আমাদের একটি অ্যারে দেওয়া হয়েছে, এবং আমাদের দুটি ধরণের প্রশ্নের উত্তর দিতে হবে৷
- টাইপ 0 − আমাদের x(প্রদত্ত মান) এর চেয়ে বা সমান বড় উপাদানের সংখ্যা গণনা করতে হবে।
- টাইপ 1 − আমাদের 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 : No elements greater than or equal to 50.
x = 40, q = 1 : 45 is greater than 40.
x = 30, q = 0 : three elements 30, 40, 45 are greater than or equal to 30. সমাধান খোঁজার পদ্ধতি
সমাধান খুঁজতে আমরা দুটি ভিন্ন পদ্ধতি ব্যবহার করতে পারি। প্রথমে আমরা ব্রুট ফোর্স সলিউশন ব্যবহার করব এবং তারপর পরীক্ষা করব যে এটি উচ্চতর সীমাবদ্ধতার জন্য কাজ করতে পারে কি না। যদি তা না হয়, তাহলে আমরা আমাদের সমাধান অপ্টিমাইজ করতে এগিয়ে যাই।
ব্রুট ফোর্স অ্যাপ্রোচ
এই পদ্ধতিতে, আমরা সমস্ত q প্রশ্নগুলির জন্য অ্যারের মাধ্যমে অতিক্রম করব এবং প্রদত্ত শর্তগুলি পূরণ করে এমন সংখ্যাগুলি খুঁজে বের করব৷
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void query(int *arr, int n, int type, int val) {
int count = 0; // answer
if(!type) { // when type 0 query is asked
for(int i = 0; i < n; i++) {
if(arr[i] >= val)
count++;
}
} else { // when type 1 query is asked
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]); // size of our array
query(ARR, n, 0, 50); // query 1
query(ARR, n, 1, 40); // query 2
query(ARR, n, 0, 30); // query 3
return 0;
} আউটপুট
0 1 3
উপরের পদ্ধতিতে, আমরা কেবল অ্যারের মধ্য দিয়ে যাচ্ছি এবং প্রশ্নের উত্তর গণনা করছি; এই পদ্ধতিটি প্রদত্ত উদাহরণগুলির জন্য কাজ করছে, কিন্তু যদি আমরা উচ্চতর সীমাবদ্ধতার সম্মুখীন হই তবে এই পদ্ধতিটি ব্যর্থ হবে কারণ প্রোগ্রামটির সামগ্রিক সময় জটিলতা হল O(N*Q) যেখানে N হল আমাদের অ্যারের আকার এবং Q হল প্রশ্নের সংখ্যা তাই এখন আমরা এই পদ্ধতিটিকে অপ্টিমাইজ করব যাতে এটি উচ্চ সীমাবদ্ধতার জন্যও কাজ করে।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা প্রদত্ত মানের উপরের বাউন্ড এবং লোয়ার বাউন্ড খুঁজে বের করতে বাইনারি অনুসন্ধান ব্যবহার করব। আমরা প্রথমে বাইনারি সার্চ ব্যবহার করে আমাদের অ্যারে সাজাই এবং তারপর সেই অনুযায়ী আমাদের লোয়ার বাউন্ড এবং আপার বাউন্ড ফাংশন প্রয়োগ করি।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void lowerbound(int *arr, int n, int val) {
int l = -1, r = n;
while(r - l > 1) { // binary searching the answer
int mid = (l+r)/2;
if(arr[mid] >= val)
r = mid;
else
l = mid;
}
if(r == n) // if r is unmoved then it means there is no element that satisfy the condition
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) { // binary searching the answer
int mid = (l+r)/2;
if(arr[mid] > val)
r = mid;
else
l = mid;
}
if(r == n)// if r is unmoved then it means there is no element that satisfy the condition
cout << "0\n";
else
cout << n - r <<"\n";
}
void query(int *arr, int n, int type, int val) {
if(!type) // if type == 0 we call lower bound function
lowerbound(arr, n, val);
else // if type == 1 we call upperbound function
upperbound(arr, n, val);
}
int main() {
int arr[] = { 1, 2, 3, 4 };
int n = sizeof(arr)/sizeof(arr[0]); // size of our array
sort(arr, arr+n); // sorting the array
query(arr, n, 0, 5); // query 1
query(arr, n, 1, 3); // query 2
query(arr, n, 0, 3); // query 3
return 0;
} আউটপুট
0 1 2
উপরের কোডটি একটি বাইনারি অনুসন্ধানে কাজ করে যা আমাদের সময় জটিলতাকে উল্লেখযোগ্যভাবে হ্রাস করে। এইভাবে আমাদের চূড়ান্ত জটিলতা হয়ে ওঠে O(NlogN) , যেখানে N হল আমাদের অ্যারের আকার।
উপরের কোডের ব্যাখ্যা
এই পদ্ধতিতে, আমরা প্রদত্ত মানের উপরের সীমা এবং নিম্ন সীমা খুঁজে বের করতে বাইনারি অনুসন্ধান ব্যবহার করব। এখন বাইনারি অনুসন্ধানের জন্য, আমরা প্রথমে আমাদের অ্যারে সাজাই কারণ এটি শুধুমাত্র সাজানো অ্যারেগুলির সাথে কাজ করে। আমরা আমাদের লোয়ার বাউন্ড এবং আপার বাউন্ড ফাংশন তৈরি করি যা আমাদেরকে প্রথম সংখ্যা খুঁজে পেতে সাহায্য করে যা যথাক্রমে টাইপ 0, টাইপ 1 শর্ত পূরণ করে, এখন যেমন আমরা অ্যারে সাজিয়েছি। আমরা প্রথম সংখ্যাটি পেয়েছি যা শর্তটিকে সাহায্য করে, তাই এই উপাদানটির পরের উপাদানগুলিও শর্ত অনুসরণ করে, তাই আমরা এই উপাদানটির সূচকের পার্থক্য N(আমাদের অ্যারের আকার) দিয়ে প্রিন্ট করি।
উপসংহার
এই নিবন্ধে, আমরা বাইনারি অনুসন্ধান ব্যবহার করার চেয়ে বেশি এবং কম নয় এমন প্রশ্নের সমাধান করার জন্য একটি সমস্যা সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি ( স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে৷
