जावास्क्रिप्ट में सरणी में अजीबोगरीब जोड़े ढूँढना

समस्या

हमें एक जावास्क्रिप्ट फ़ंक्शन लिखना आवश्यक है जो पहले और एकमात्र तर्क के रूप में इंटीजर, एआर की एक सरणी लेता है।

हमारे फ़ंक्शन को ऐसे सभी सूचकांक जोड़े (i, j) की घटना की गणना करनी चाहिए जो निम्नलिखित शर्तों को पूरा करते हैं -

• मैं <जे, और

• गिरफ्तारी [i]> 2 * गिरफ्तार [जे]

उदाहरण के लिए, यदि फ़ंक्शन का इनपुट है -

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));

कोड स्पष्टीकरण

हमने यहां एक बाइनरी इंडेक्स ट्री (बीआईटी) का उपयोग किया है -

बाइनरी इंडेक्स ट्री या बीआईटी को एक सरणी के रूप में दर्शाया जाता है। सरणी को BITree [] होने दें। बाइनरी इंडेक्स ट्री का प्रत्येक नोड इनपुट सरणी के कुछ तत्वों के योग को संग्रहीत करता है। बाइनरी इंडेक्स ट्री का आकार इनपुट सरणी के आकार के बराबर है।

आउटपुट

और कंसोल में आउटपुट होगा -

3