এই নিবন্ধে আমরা প্রদত্ত পরিসরে উপস্থিত উপাদানগুলির সংখ্যা খুঁজে বের করার একটি সমস্যা নিয়ে আলোচনা করব যার একটি kth বিট সেট রয়েছে, উদাহরণস্বরূপ −
Input : arr[] = { 4, 5, 7, 2 }
Query 1: L = 2, R = 4, K = 4
Query 2: L = 3, R = 5, K = 1
Output :
0
1 আমরা একটি নৃশংস শক্তি পদ্ধতির মাধ্যমে এই সমস্যাটি সমাধান করতে যাচ্ছি এবং এই পদ্ধতিটি উচ্চ সীমাবদ্ধতার জন্য কাজ করতে পারে কিনা তা দেখতে যাচ্ছি। যদি না হয়, তাহলে আমরা একটি নতুন দক্ষ পদ্ধতির কথা ভাবার চেষ্টা করি৷
ব্রুট ফোর্স অ্যাপ্রোচ
এই পদ্ধতিতে, আমরা কেবল পরিসরের মধ্য দিয়ে যেতে যাচ্ছি এবং প্রতিটি উপাদানের জন্য পরীক্ষা করব যে এটি kth বিট সেট করা আছে কি না, যদি হ্যাঁ, তাহলে আমরা গণনা বাড়িয়ে দিই।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { // to check if kth bit is set
if (n & (1 << (k - 1)))
return true;
return false;
}
int query(int L, int R, int K, int arr[]) {
int count = 0; // counter to keep count of number present in the range
for (int i = L; i <= R; i++) { // traversing the range
if (Kset(arr[i], K)) {
count++;
}
}
return count;
}
int main() {
int arr[] = { 4, 5, 7, 2 }; // given array
int n = sizeof(arr) / sizeof(arr[0]); // size of our array
int queries[][3] = { // given L, R and k
{ 2, 4, 4 },
{ 3, 5, 1 }
};
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
int L = queries[i][0] - 1;
int R = queries[i][1] - 1;
int K = queries[i][2];
cout << query(L, R, K, arr) << "\n";
}
return 0;
} আউটপুট
0 1
উপরের পদ্ধতিতে O(N*Q) এর একটি সময় জটিলতা রয়েছে যেখানে N হল আমাদের অ্যারের আকার এবং Q হল আমাদের এখন দেওয়া প্রশ্নের সংখ্যা; আপনি দেখতে পাচ্ছেন, এই পদ্ধতিটি উচ্চ সীমাবদ্ধতার জন্য উপযুক্ত নয় কারণ এটি অনেক বেশি সময় নেবে তাই এখন আমরা দক্ষ পদ্ধতির একটি প্রোগ্রাম তৈরি করার চেষ্টা করব৷
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা একটি 2-ডি প্রিফিক্স সমষ্টি অ্যারে বজায় রাখব যা প্রতিটি সূচক পর্যন্ত ব্যবহৃত প্রতিটি বিটের গণনা রাখবে, এবং তারপর আমরা O(1) জটিলতায় উত্তরটি গণনা করতে পারি।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
#define bits 32 // number of bits
int P[100000][bits+1];
bool Kset(int n, int k) {
if (n & (1 << (k - 1)))
return true;
return false;
}
void prefixArray(int n, int arr[]) { // building the prefix array
for (int i = 0; i <= bits; i++) {
P[0][i] = 0; // setting every bits initial count = 0
}
for (int i = 0; i < n; i++) {
for (int j = 1; j <= bits; j++) {
bool flag = Kset(arr[i], j);
if (i) // we add previous count to the latest count(0)
P[i][j] = P[i - 1][j];
if (flag) { // if jth bit is set so we increase the count
P[i][j]++;
}
}
}
}
int query(int L, int R, int K) {
if (L) // if L not equal to 0 then we return the prefix at R subtracted with prefix at L-1
return P[R][K] - P[L - 1][K];
else
return P[R][K];
}
int main() {
int arr[] = { 8, 9, 1, 3 }; // given array
int n = sizeof(arr) / sizeof(arr[0]); // size of given array
int queries[][3] = {
{ 1, 3, 4 },
{ 2, 4, 1 }
};
prefixArray(n, arr); // calling the function to create prefix array
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
int L = queries[i][0] - 1;
int R = queries[i][1] - 1;
int K = queries[i][2];
cout << query(L, R, K) << "\n";
}
return 0;
} আউটপুট
2 3
যেহেতু আমরা প্রিফিক্স অ্যারে বজায় রাখছি যা আমাদেরকে O(1) তে উত্তর খুঁজতে সাহায্য করছে তাই এর দ্বারা, আমাদের সময় জটিলতা মারাত্মকভাবে কমে O(N), যেখানে N হল আমাদের প্রদত্ত অ্যারের আকার।
উপরের কোডের ব্যাখ্যা
এই প্রোগ্রামে, আমরা অ্যারের প্রতিটি সূচকের জন্য একটি প্রিফিক্স কাউন্টার বজায় রাখি যা সূচক পর্যন্ত ব্যবহৃত প্রতিটি বিট গণনা করে। আমরা এখন আমাদের অ্যারের জন্য এই গণনাটি তৈরি করি কারণ আমাদের কাছে আমাদের কাছে সংরক্ষিত প্রতিটি বিটের উপসর্গ গণনা রয়েছে, তাই kth বিট গণনার জন্য, আমাদের kth বিটের উপসর্গ গণনা বিয়োগ করতে হবে R সূচকের সাথে kth বিটের উপসর্গ গণনা L- পর্যন্ত। 1 সূচক এবং এটি আমাদের উত্তর।
উপসংহার
এই নিবন্ধে, আমরা Kth বিট সেটের সাথে একটি পরিসরে অ্যারের উপাদানগুলির সংখ্যার জন্য প্রশ্নের সমাধান করার জন্য একটি সমস্যা সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি ( স্বাভাবিক এবং দক্ষ) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা একই প্রোগ্রাম অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় লিখতে পারি। আমরা আশা করি আপনার এই নিবন্ধটি সহায়ক হবে৷
