এই আর্টিকেলে, আমরা একটি সমস্যা আলোচনা করব যেখানে দেওয়া রেঞ্জে কতগুলো উপাদানের K-তম বিট সেট (১) আছে তা বের করতে হবে। উদাহরণস্বরূপ:
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
আমরা এই সমস্যাকে ব্রুট ফোর্স পদ্ধতিতে সমাধান করব এবং দেখব এটি উচ্চ কনস্ট্রেইন্টের জন্য কাজ করে কিনা। না হলে দক্ষ পদ্ধতি চিন্তা করব।
ব্রুট ফোর্স পদ্ধতি
এই পদ্ধতিতে, আমরা সিম্পলি রেঞ্জের মাধ্যমে যাব এবং প্রতিটি উপাদানের K-তম বিট সেট আছে কিনা চেক করব। হ্যাঁ হলে কাউন্ট বাড়াব।
উদাহরণ
#include<bits/stdc++.h> using namespace std; #define MAX_BITS 32 bool Kset(int n, int k) { // K-তম বিট সেট আছে কিনা চেক if (n & (1 << (k - 1))) return true; return false; } int query(int L, int R, int K, int arr[]) { int count = 0; // রেঞ্জে থাকা উপাদান কাউন্ট for (int i = L; i <= R; i++) { // রেঞ্জ ট্রাভার্স if (Kset(arr[i], K)) { count++; } } return count; } int main() { int arr[] = { 4, 5, 7, 2 }; // দেওয়া অ্যারে int n = sizeof(arr) / sizeof(arr[0]); // অ্যারের আকার int queries[][3] = { // দেওয়া L, R এবং K { 2, 4, 4 }, { 3, 5, 1 } }; int q = sizeof(queries) / sizeof(queries[0]); // কোয়েরি সংখ্যা 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 হল কোয়েরি সংখ্যা। এটি উচ্চ কনস্ট্রেইন্টের জন্য উপযুক্ত নয়, তাই আমরা দক্ষ পদ্ধতি করব।
দক্ষ পদ্ধতি
এই পদ্ধতিতে, আমরা একটি ২-ডি প্রিফিক্স সম অ্যারে মেইনটেইন করব যা প্রতিটি সূচক পর্যন্ত প্রতিটি বিটের কাউন্ট রাখবে, এবং তারপর O(1) কমপ্লেক্সিটিতে উত্তর বের করব।
উদাহরণ
#include<bits/stdc++.h> using namespace std; #define bits 32 // বিটের সংখ্যা 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[]) { // প্রিফিক্স অ্যারে তৈরি for (int i = 0; i <= bits; i++) { P[0][i] = 0; // প্রতিটি বিটের প্রাথমিক কাউন্ট ০ } for (int i = 0; i < n; i++) { for (int j = 1; j <= bits; j++) { bool flag = Kset(arr[i], j); if (i) // পূর্বের কাউন্ট যোগ করুন P[i][j] = P[i - 1][j]; if (flag) { // j-তম বিট সেট থাকলে কাউন্ট বাড়ান P[i][j]++; } } } } int query(int L, int R, int K) { if (L) // L যদি ০ না হয় তবে R-এ প্রিফিক্স থেকে L-1-এ প্রিফিক্স বিয়োগ করুন return P[R][K] - P[L - 1][K]; else return P[R][K]; } int main() { int arr[] = { 8, 9, 1, 3 }; // দেওয়া অ্যারে int n = sizeof(arr) / sizeof(arr[0]); // অ্যারের আকার int queries[][3] = { { 1, 3, 4 }, { 2, 4, 1 } }; prefixArray(n, arr); // প্রিফিক্স অ্যারে তৈরির ফাংশন কল int q = sizeof(queries) / sizeof(queries[0]); // কোয়েরি সংখ্যা 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 হল দেওয়া অ্যারের আকার।
উপরোক্ত কোডের ব্যাখ্যা
এই প্রোগ্রামে, আমরা অ্যারেতে প্রতিটি সূচকের জন্য একটি প্রিফিক্স কাউন্টার মেইনটেইন করি যা সেই সূচক পর্যন্ত ব্যবহৃত প্রতিটি বিট গণনা করে। আমরা আমাদের অ্যারের জন্য এই কাউন্ট তৈরি করি। এখন যেহেতু আমাদের কাছে প্রতিটি বিটের প্রিফিক্স কাউন্ট আছে, K-তম বিটের কাউন্টের জন্য আমাদের R সূচক পর্যন্ত K-তম বিটের প্রিফিক্স কাউন্ট থেকে L-1 সূচক পর্যন্ত K-তম বিটের প্রিফিক্স কাউন্ট বিয়োগ করতে হবে এবং সেটিই আমাদের উত্তর।
উপসংহার
এই আর্টিকেলে, আমরা একটি রেঞ্জে K-তম বিট সেট থাকা অ্যারে উপাদান সংখ্যা নির্ণয়ের কোয়েরি সমাধান করেছি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (সাধারণ ও দক্ষ) শিখেছি। একই প্রোগ্রামটি C, Java, Python এবং অন্যান্য ভাষায়ও লিখা যায়। আশা করি আপনি এই আর্টিকেলটিকে উপকারী পাবেন।
