Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
}
#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):
# Write your code here
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()