Algorithm


Problem Name: Data Structures - Array Pairs

Problem Link: https://www.hackerrank.com/challenges/array-pairs/problem?isFullScreen=true

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 & Try With Live Editor

#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()
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Tree Coordinates solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Array and simple queries solution in Hackerrank - Hacerrank solution C, C++, java,js, Python