সমস্যা
আমাদের একটি জাভাস্ক্রিপ্ট ফাংশন লিখতে হবে যা একটি ইন্টিজার অ্যারে arr একমাত্র আর্গুমেন্ট হিসেবে নেবে।
ফাংশনটি সব এমন ইন্ডেক্স জোড়া (i, j) এর ঘটনা গণনা করবে যেগুলো নিচের শর্তগুলো পূরণ করে:
i < j, এবং
arr[i] > 2 * arr[j]
উদাহরণ:
const input = [2, 4, 3, 5, 1];
আউটপুট হবে:
const output = 3;
আউটপুট ব্যাখ্যা:
তিনটি জোড়া হচ্ছে: [4, 1], [3, 1] এবং [5, 1]
উদাহরণ
কোডটি নিচের মতো (বাইনারি ইন্ডেক্সড ট্রি / BIT):
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)); কোড ব্যাখ্যা
এখানে বাইনারি ইন্ডেক্সড ট্রি (BIT) ব্যবহার করা হয়েছে। BIT একটি অ্যারে হিসেবে রিপ্রেজেন্ট করা হয়। BIT-এর প্রতিটি নোড ইনপুট অ্যারের কিছু উপাদানের যোগফল স্টোর করে।
আউটপুট
কনসোলে আউটপুট:
3
