এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যাতে N সংখ্যক নাম্বার আছে এবং একটি ইন্টিজার মান X। আমাদের কাজ হল N সংখ্যার প্রিফিক্স সামে X-র চেয়ে বড় বা সমান প্রথম এলিমেন্ট বের করা বাইনারি লিফটিং ব্যবহার করে।
প্রিফিক্স সাম (Prefix Sum) হল একটি অ্যারে যেটির প্রতিটি এলিমেন্ট হল প্রাথমিক অ্যারেতে সেই ইনডেক্স পর্যন্ত সব এলিমেন্টের যোগফল।
উদাহরণ - array[] = {5, 2, 9, 4, 1}
prefixSumArray[] = {5, 7, 16, 20, 21}
উদাহরণ দেখি:
ইনপুট: arr[] = {5, 2, 9, 4, 1}, X = 19 আউটপুট: 3
সমাধানের পদ্ধতি
এখানে আমরা বাইনারি লিফটিং কনসেপ্ট ব্যবহার করে সমাধান করব। বাইনারি লিফটিং হল দেয়া সংখ্যার মান ২-এর ঘাত দিয়ে বাড়ানো (বিট ফ্লিপ করে) ০ থেকে N পর্যন্ত।
আমরা একটি কনসেপ্ট ব্যবহার করব যা বাইনারি ট্রি লিফটিং-এর মতো। যেখানে আমরা 'P' ইনডেক্সের প্রাথমিক মান বের করব। এটি বিট ফ্লিপ করে বাড়াতে থাকব নিশ্চিত করে যে মান X-র চেয়ে বড় হয় না। এখন, আমরা এই পজিশন 'P'-এর সাথে লিফটিং ধরে নেব।
এজন্য, আমরা নম্বারের বিট ফ্লিপ করা শুরু করব যেন i-th বিট ফ্লিপ করলে সাম X-র চেয়ে বড় হয় না। এখন 'P'-এর ভ্যালু বেসড দুটি কেস থাকবে -
অথবা টার্গেট পজিশন থাকে 'position + 2^i' এবং 'position + 2^(i+1)' এর মাঝপথে যেখানে i-th লিফটিং মান বাড়িয়েছে। অথবা, টার্গেট পজিশন থাকে 'position' এবং 'position + 2^i' এর মাঝপথে।
এটি ব্যবহার করে আমরা ইনডেক্স পজিশন বের করব।
উদাহরণ
#include <iostream> #include <math.h> using namespace std; void generatePrefixSum(int arr[], int prefSum[], int n){ prefSum[0] = arr[0]; for (int i = 1; i < n; i++) prefSum[i] = prefSum[i - 1] + arr[i]; } int findPreSumIndexBL(int prefSum[], int n, int x){ int P = 0; int LOGN = log2(n); if (x <= prefSum[0]) return 0; for (int i = LOGN; i >= 0; i--) { if (P + (1 << i) < n && prefSum[P + (1 << i)] < x) { P += (1 << i); } } return P + 1; } int main(){ int arr[] = { 5, 2, 9, 4, 1 }; int X = 19; int n = sizeof(arr) / sizeof(arr[0]); int prefSum[n] = { 0 }; generatePrefixSum(arr, prefSum, n); cout<<"The index of first elements of the array greater than the given number is "; cout<<findPreSumIndexBL(prefSum, n, X); return 0; }
আউটপুট
The index of first elements of the array greater than the given number is 3
