C++ এ বাইনারি লিফটিং ব্যবহার করে N সংখ্যার উপসর্গ যোগফলের X এর থেকে বড় বা সমান প্রথম উপাদান

এই সমস্যায়, আমাদেরকে একটি অ্যারে দেওয়া হয়েছে যা N সংখ্যা এবং একটি পূর্ণসংখ্যা মান x নিয়ে গঠিত। আমাদের কাজ হল বাইনারি লিফটিং ব্যবহার করে N সংখ্যার উপসর্গ যোগে X এর থেকে বড় বা সমান প্রথম উপাদান খুঁজে বের করার জন্য একটি প্রোগ্রাম তৈরি করা .

উপসর্গ যোগ একটি অ্যারের উপাদানগুলির একটি অ্যারে যার প্রতিটি উপাদান প্রাথমিক অ্যারেতে সেই সূচক পর্যন্ত সমস্ত উপাদানের সমষ্টি৷

উদাহরণ − অ্যারে[] ={5, 2, 9, 4, 1}

prefixSumArray[] ={5, 7, 16, 20, 21}

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

Input: arr[] = {5, 2, 9, 4, 1}, X = 19
Output: 3

সমাধান পদ্ধতি

এখানে, আমরা বাইনারী উত্তোলন ধারণা ব্যবহার করে সমস্যার সমাধান করব . বাইনারি লিফটিং প্রদত্ত সংখ্যার মান 0 থেকে N পর্যন্ত 2 এর ক্ষমতা দ্বারা (বিট ফ্লিপ করার মাধ্যমে সম্পন্ন) বৃদ্ধি করছে।

আমরা বাইনারি গাছ তোলার মতো একটি ধারণা বিবেচনা করব যেখানে আমরা 'P' সূচকের প্রাথমিক মান খুঁজে পাব। মানটি X-এর চেয়ে বেশি নয় তা নিশ্চিত করে বিটগুলি ফ্লিপ করে এটি বৃদ্ধি করা হয়। এখন, আমরা এই অবস্থান 'P'-এর সাথে উত্তোলনের কথা বিবেচনা করব।

এর জন্য, আমরা সংখ্যার বিটগুলি এমনভাবে ফ্লিপ করা শুরু করব যাতে i-th বিট ফ্লিপের যোগফল X-এর থেকে বেশি না হয়৷ এখন, আমাদের কাছে 'P'-এর মানের উপর ভিত্তি করে দুটি কেস রয়েছে -

হয় লক্ষ্য অবস্থান 'অবস্থান + 2^i এর মধ্যে অবস্থিত ' এবং 'অবস্থান + 2^(i+1) ' যেখানে ith লিফট মান বাড়িয়েছে। অথবা, লক্ষ্য অবস্থানটি 'অবস্থানের মধ্যে অবস্থিত ' এবং 'অবস্থান + 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