## Algorithm

Problem Name: Data Structures - Array Pairs

In this HackerRank in Data Structures - Array Pairssolutions

Consider an array of n integers, A = [a1,a2, ... , an]. Find and print the total number of (i,j) pairs such that ai * aj <= max(ai,ai + 1, ... , aj) where i > j.

Input Format

The first line contains an integer, n, denoting the number of elements in the array.

The second line consists of n pace-separated integers describing the respective values of a1,a2, ... , an.

Constraints

• 1 <= n <= 5 * 10**5
• 1 <= ai <= 10**9

Output Format

Print a long integer denoting the total number (i,j) pairs satisfying ai * aj <= max(ai,ai + 1, ... , aj) where i < j

Sample Input

``````5
1 1 2 4 2
``````

Sample Output

``````8
``````

Explanation

There are eight pairs of indices satisfying the given criteria: (1,2),(1,3), (1,4),(1,5),(2,3),(2,4),(2,5), and (3,5) Thus, we print 8 as our answer.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>
using namespace std;

int numOfElements;            // first line
int inputArray[1000011];    // inputArray second line
int leftPart[1000011];        // Left part of array
int rightPart[1000011];        // Right Part of array
std::vector<int> lookupMatrix[1000011];        // Lookup Matrix
long long int binaryIndexTree[1000011];     // Binary Index Tree matrix representation

/*
* Update a node in Binary Index Tree (BIT) at
* a given index in BIT. The give value 'val'
* is added to binaryIndexTree[i] and all (maxn)
* of its ancestors in tree.
*/
void updateBinaryIndexTree(int ind, int val, int maxn) {
while(ind  < = maxn) {
binaryIndexTree[ind] += val;
ind += (ind & -ind);
}
}

/*
* Return minimum of elements in range from
* index to the end of binary index tree.
*/
long long int rangeMinimumQuery(int index) {
long long int ans = 0;
while(index > 0) {
ans += binaryIndexTree[index];
index -= (index & -index);
}
return ans;
}

/*
* Return the index of element in Disjoint Union Set (DSU)
* by taking the element x and size of disjointSetUnionSize
* as a parameters.
*/
int findElementIndexInDSU(int x, vector<int> disjointSetUnionSize) {
if(disjointSetUnionSize.back() <= x) return disjointSetUnionSize.size();
return upper_bound(disjointSetUnionSize.begin(), disjointSetUnionSize.end(), x) - disjointSetUnionSize.begin();
}

int main() {
ios_base::sync_with_stdio(0);
cin.tie(0>;

cin >> numOfElements;
set < int> dsu;            // Disjoint Set Union
unordered_map<int, int> disjointSetUnionMap;

// Construct Disjoint Set Union.
for(int i = 1; i  < = numOfElements; i++) {
cin >> inputArray[i];
//assert(inputArray[i] >= 1 and inputArray[i]  < = 1000000000);
dsu.insert(inputArray[i]);
}

// Extract and Process Set Ordered Pairs
vector < pair 0 and orderedPairs.back().first < inputArray[i]) orderedPairs.pop_back();
if(orderedPairs.size() == 0) leftPart[i] = 1;
else {
leftPart[i] = orderedPairs.back().second + 1;
}
orderedPairs.push_back(make_pair(inputArray[i], i));
}
orderedPairs.clear();
for(int i = numOfElements; i >= 1; i--) {
while(orderedPairs.size() > 0 and orderedPairs.back().first <= inputArray[i]) orderedPairs.pop_back();
if(orderedPairs.size() == 0) rightPart[i] = numOfElements;
else {
rightPart[i] = orderedPairs.back().second - 1;
}
orderedPairs.push_back(make_pair(inputArray[i], i));
}

// Add entry to Lookup Matrix
for(int i = 1; i  < = numOfElements; i++) {
if(i - leftPart[i] <= rightPart[i] - i) {
for(int j = leftPart[i]; j  <  i; j++) {
lookupMatrix[i - 1].push_back(-inputArray[i] / inputArray[j]);
lookupMatrix[rightPart[i]].push_back(inputArray[i] / inputArray[j]);
}

lookupMatrix[i].push_back(-1);
lookupMatrix[rightPart[i]].push_back(1);
} else {

for(int j = i + 1; j  < = rightPart[i]; j++) {
lookupMatrix[leftPart[i] - 1].push_back(-inputArray[i] / inputArray[j]);
lookupMatrix[i].push_back(inputArray[i] / inputArray[j]);
}
lookupMatrix[leftPart[i] - 1].push_back(-1);
lookupMatrix[i - 1].push_back(1);
}
}

int maxn = dsu.size(> + 2;
int cnt = 1;
for(set < int>::iterator it = dsu.begin(); it != dsu.end(); it++) {
disjointSetUnionMap[*it] = cnt++;
}

long long int ans = 0;
int range;
vector<int> dsuSize = vector<int>(dsu.begin(), dsu.end());
for(int i = 1; i  < = numOfElements; i++) {
updateBinaryIndexTree(disjointSetUnionMap[inputArray[i]], 1, maxn);
for(int j = 0; j  <  lookupMatrix[i].size(); j++) {
range = findElementIndexInDSU(abs(lookupMatrix[i][j]),dsuSize);
if(lookupMatrix[i][j] < 0) {
ans -= rangeMinimumQuery(range);
} else {
ans += rangeMinimumQuery(range>;
}
}
}

cout << ans;
}

``````
Copy The Code &

### #2 Code Example with Python Programming

```Code - Python Programming```

``````
#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'solve' function below.
#
# The function is expected to return a LONG_INTEGER.
# The function accepts INTEGER_ARRAY arr as parameter.
#

def solve(arr):
i=1
res=0
while True:
if i==len(arr)-1:
break
for j in range(i+1,len(arr)+1):
temp=arr[i-1:j]
if (arr[i-1]*arr[j-1])<=max(temp):
res+=1
i+=1
return res

if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')

arr_count = int(input().strip())

arr = list(map(int, input().rstrip().split()))

result = solve(arr)

fptr.write(str(result) + '\n')

fptr.close()
``````
Copy The Code &