জাভাস্ক্রিপ্টে অ্যারেতে অদ্ভুত জোড়া খোঁজা

সমস্যা

আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা প্রথম এবং একমাত্র যুক্তি হিসাবে পূর্ণসংখ্যা, arr-এর একটি অ্যারে নেয়৷

আমাদের ফাংশনটি এই ধরনের সমস্ত সূচক জোড়া (i, j) এর উপস্থিতি গণনা করা উচিত যা নিম্নলিখিত শর্তগুলি পূরণ করে -

• আমি

• arr[i]> 2 * arr[j]

উদাহরণস্বরূপ, যদি ফাংশনে ইনপুট হয় −

const input = [2, 4, 3, 5, 1];

তারপর আউটপুট −

const output = 3;

আউটপুট ব্যাখ্যা:

কারণ তিনটি কাঙ্ক্ষিত জোড়া হল −

[4, 1], [3, 1] and [5, 1]

উদাহরণ

এর জন্য কোড হবে −

const arr = [2, 4, 3, 5, 1];
const peculiarPairs = (arr = []) => {
   let count = 0;
   let copy = arr.slice().sort((a,b)=> a - b);
   let bit = new Array(arr.length+1).fill(0);
   for (const num of arr){
      count += search(bit, indexed(copy, 2*num+1));
      bit = insert(bit, indexed(copy, num));
   };
   return count;
};
const search = (bit, i) => {
   let sum = 0;
   while (i < bit.length){
      sum += bit[i];
      i += i & -i;
   }
   return sum;
}
const insert = (bit, i) => {
   while (i > 0){
      bit[i] += 1;
      i -= i & -i;
   }
   return bit;
}
const indexed = (arr, val) => {
   let l = 0, r = arr.length-1, m = 0;
   while (l <= r) {
      m = l + ((r-l) >> 1);
      if (arr[m] >= val){
         r = m-1;
      }else{
         l = m+1;
      }
   }
   return l+1;
}
console.log(peculiarPairs(arr));

কোড ব্যাখ্যা

আমরা এখানে একটি Binary Indexed Tree (BIT) -

বাইনারি ইনডেক্সড ট্রি বা বিআইটি একটি অ্যারে হিসাবে উপস্থাপন করা হয়। অ্যারেটি BITree [] হতে দিন। বাইনারি ইনডেক্সড ট্রির প্রতিটি নোড ইনপুট অ্যারের কিছু উপাদানের যোগফল সঞ্চয় করে। বাইনারি ইনডেক্সড ট্রির আকার ইনপুট অ্যারের আকারের সমান।

আউটপুট

এবং কনসোলে আউটপুট হবে −

3