समस्या
हमें एक JavaScript फ़ंक्शन लिखना है जो पहली और एकमात्र आर्ग्युमेंट के रूप में पूर्णांकों की एक सरणी arr लेता है।
हमारे फ़ंक्शन को उन सभी इंडेक्स जोड़े (i, j) की घटनाओं को गिनना चाहिए जो निम्न शर्तों को पूरा करते हैं:
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));कोड व्याख्या
हमने यहां बाइनरी इंडेक्स्ड ट्री (BIT) का उपयोग किया है:
बाइनरी इंडेक्स्ड ट्री या BIT को सरणी के रूप में दर्शाया जाता है। मान लीजिए सरणी BITree[] है। बाइनरी इंडेक्स्ड ट्री का प्रत्येक नोड इनपुट सरणी के कुछ तत्वों का योग संग्रहीत करता है। बाइनरी इंडेक्स्ड ट्री का आकार इनपुट सरणी के आकार के बराबर होता है।
आउटपुट
कंसोल में आउटपुट होगा:
3
