HackerRank Triplets problem solution

In this HackerRank Triplets problem solution, you are given an integer array that does not contain more than two elements of the same value. we need to find out how many distinct ascending triplets are present in the array.

Problem solution in Python programming.

root = 1
last_level = 262144
tree_1 = [0 for i in range(last_level*2 + 1)]
tree_2 = [0 for i in range(last_level*2 + 1)]
tri = [0 for i in range(100048)]

#zle jest, tzn kod a nie ogolnie
def less_than(x, tab):
    index = root
    sum = 0
    c_level = last_level
    while(index < x+last_level):

        if x <  c_level // 2:
            index *= 2
        else:
            index *= 2
            sum += tab[index]
            index += 1
            x -= (c_level//2)
        # print(x)
        # print(c_level)

        c_level //= 2


    return sum

def add_elem_1(x):
    tree = tree_1
    index = x + last_level
    tree[index] = 1
    index //=2

    while index > 0:
        tree[index] = tree[2*index] + tree[2*index + 1]
        index //=2

def add_elem_2(x):
    tree = tree_2
    index = x + last_level
    tree[index] = less_than(x, tree_1)
    index //=2

    while index > 0:
        tree[index] = tree[2*index] + tree[2*index + 1]
        index //=2

n = int(input())
n_l = input()
input_array = [int(x) for x in n_l.split()]

for i in input_array:
    add_elem_1(i)
    add_elem_2(i)
    # print(less_than(i, tree_2))
    # print(less_than(100, tree_1), less_than(100,tree_2))
    tri[i] = less_than(i, tree_2)

sum = 0
for i in tri:
    sum += i
print(sum)

Problem solution in Java Programming.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {
    public static class Triplets {

        long[] lSmaller, rLarger, treeArray;
    int[] dscArray, lFlags, rFlags;
    int size, count = 0;

    Triplets(int aSize, long[] inputArray) {
        size = aSize;
        lSmaller = new long[size];
        rLarger = new long[size];
        dscArray = new int[size];
        long[] tmpArray = Arrays.copyOf(inputArray, inputArray.length);
        Arrays.sort(tmpArray);
        HashMap<Long, Integer> tmpMap = new HashMap<>(size);
        for (int i = 0; i < size; i++) {
            if (!tmpMap.containsKey(tmpArray[i])) {
                count++;
                tmpMap.put(tmpArray[i], count);
            }
        }
        count++;
        treeArray = new long[count];
        lFlags = new int[count];
        rFlags = new int[count];
        for (int i = 0; i < size; i++) {
            dscArray[i] = tmpMap.get(inputArray[i]);
        }

    }

    void update(int idx) {
        while (idx < count) {
            treeArray[idx]++;

            idx += (idx & -idx);
        }
    }

    long read(int index) {
        int sum = 0;
        while (index > 0) {
            sum += treeArray[index];
            index -= (index & -index);
        }
        return sum;
    }

    void countLeftSmaller() {
        Arrays.fill(treeArray, 0);
        Arrays.fill(lSmaller, 0);
        Arrays.fill(lFlags, 0);
        for (int i = 0; i < size; i++) {
            int val = dscArray[i];
            lSmaller[i] = read(val - 1);
            if (lFlags[val] == 0) {
                update(val);
                lFlags[val] = i + 1;
            } else {
                lSmaller[i] -= lSmaller[lFlags[val] - 1];
            }
        }
    }

    void countRightLarger() {

        Arrays.fill(treeArray, 0);
        Arrays.fill(rLarger, 0);
        Arrays.fill(rFlags, 0);
        for (int i = size - 1; i >= 0; i--) {
            int val = dscArray[i];
            rLarger[i] = read(count - 1) - read(val);
            if (rFlags[val] == 0) {
                update(val);
                rFlags[val] = i + 1;
            }
        }
    }

    long countTriplets() {
        long sum = 0;
        for (int i = 0; i < size; i++) {
            sum += lSmaller[i] * rLarger[i];
        }
        return sum;
    }
}

    // Complete the solve function below.
    static long solve(long[] d) {
        int n = d.length;
        Triplets sol = new Triplets(n, d);
        sol.countLeftSmaller();
        sol.countRightLarger();
        return sol.countTriplets();
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int dCount = scanner.nextInt();
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        long[] d = new long[dCount];

        String[] dItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])?");

        for (int dItr = 0; dItr < dCount; dItr++) {
            long dItem = Long.parseLong(dItems[dItr]);
            d[dItr] = dItem;
        }

        long result = solve(d);

        bufferedWriter.write(String.valueOf(result));
        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Problem solution in C++ programming.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <iostream>
#include <set>
#include <vector>
#include <map>

using namespace std;

struct node{
    node *left, *right, *parent;
    int val, height, ownsize;
    long long int size;
};

node* insert(node* root, int val, int size){
    if(!root){
        node *nn = new node;
        nn->val = val;
        nn->size = nn->ownsize = size;
        nn->left = 0;
        nn->right = 0;
        return nn;
    }
    if(root->val == val){
        if(size > root->ownsize){
            root->size += size - root->ownsize;
            root->ownsize = size;
        }
    }else if(root->val > val){
        root->left = insert(root->left, val, size);
        root->size = root->left->size + (root->right ? root->right->size : 0) + root->ownsize;
    }else{
        root->right = insert(root->right, val, size);
        root->size = root->right->size + (root->left ? root->left->size : 0) + root->ownsize;
    }
    return root;
}

void inorder(node *root){
    if(root){
        inorder(root->left);
        cout<<"["<<root->val<<","<<root->size<<"] ";
        inorder(root->right);
    }
}

int countLarger(node* root, int val){
    if(root){
        if(root->val < val){
            return countLarger(root->right, val);
        }else if(root->val == val){
            return root->right ? root->right->size : 0;
        }else{
            return countLarger(root->left, val) + root->size - (root->left ? root->left->size : 0);
        }
    }
    return 0;
}

int main(){
    int N, num;
    cin>>N;
    vector<int> nums;
    vector<int> doublet(N, 0);
    for(int i = 0; i < N; i++){
        cin>>num;
        nums.push_back(num);
    }

    node root;
    root.val = nums[N - 1];
    root.height = 0;
    root.size = 1;
    root.ownsize = 1;
    root.left = 0;
    root.right = 0;

    doublet[N - 1] = 0;

    for(int i = N - 2; i >= 0; i--){
        insert(&root, nums[i], 1);
        doublet[i] = countLarger(&root, nums[i]);
    }

    root = node();
    root.val = nums[N - 1];
    root.height = 0;
    root.size = 0;
    root.ownsize = 0;
    root.left = 0;
    root.right = 0;

    long long int sum = 0;

    map<int, long long int> tri;    

    for(int i = N - 2; i >= 0; i--){
        insert(&root, nums[i], doublet[i]);
        tri[nums[i]] = countLarger(&root, nums[i]);
    }

    for(map<int, long long int>::iterator it = tri.begin(); it != tri.end(); it++){
        sum += it->second;
    }
    cout<<sum<<endl;
    return 0;
}

Problem solution in C programming.

#include<stdio.h>
#include<stdlib.h>
#define ll long long int
typedef struct _dInfo
{
unsigned int val;
int idx,sortedIdx,firstOcc,l,r,lastOcc;
}dInfo;
dInfo a[100005];
int tree[100005];
int compare(const void *a,const void *b)
{
dInfo *x1=(dInfo*)a;dInfo *x2=(dInfo*)b;
if((*x1).val<(*x2).val)return -1;
else if((*x1).val==(*x2).val && 
(*x1).idx<(*x2).idx)return -1;
return 1;
}
int compare1(const void *a,const void *b)
{
dInfo *x1=(dInfo*)a;dInfo *x2=(dInfo*)b;
if((*x1).idx<(*x2).idx)return -1;
return 1;
}
void update(int idx,int val,int maxIdx)
{
while(idx<=maxIdx)
{
tree[idx]+=val;
idx+=(idx & -idx);
}
}
int read(int idx)
{
int sum=0;
while(idx>0)
{
sum+=tree[idx];
idx-=(idx & -idx);
}
return sum;
}
int main()
{
int n,i,maxIdx;
ll triplets;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%u",&a[i].val);
a[i].idx=i;
}
qsort(a,n,sizeof(dInfo),&compare);
a[0].sortedIdx=1;
a[0].firstOcc=1;
for(i=1;i<n;i++)
{
a[i].sortedIdx=(a[i].val==a[i-1].val)?
a[i-1].sortedIdx:a[i-1].sortedIdx+1;
a[i].firstOcc=(a[i].val==a[i-1].val)?0:1;
}
a[n-1].lastOcc=1;
for(i=n-2;i>=0;i--)
{
a[i].lastOcc=(a[i].val==a[i+1].val)?0:1;
}
maxIdx=a[n-1].sortedIdx;
qsort(a,n,sizeof(dInfo),&compare1);

for(i=0;i<=maxIdx;i++)
tree[i]=0;
for(i=0;i<n;i++)
{

if(a[i].sortedIdx!=1)
a[i].l=read(a[i].sortedIdx-1);
else
a[i].l=0;
if(a[i].firstOcc)
{
update(a[i].sortedIdx,1,maxIdx);

}
}
for(i=0;i<=maxIdx;i++)
tree[i]=0;
for(i=0;i<n;i++)
a[i].sortedIdx=maxIdx+1-a[i].sortedIdx;
for(i=n-1;i>=0;i--)
{
if(a[i].sortedIdx!=1)
a[i].r=read(a[i].sortedIdx-1);
else
a[i].r=0;
if(a[i].lastOcc)
update(a[i].sortedIdx,1,maxIdx);
}
qsort(a,n,sizeof(dInfo),&compare);


for(i=0,triplets=0;i<n;i++)
{
triplets=triplets+(ll)a[i].l*(ll)a[i].r;
if(a[i].val==a[i-1].val)
triplets=triplets-(ll)a[i-1].l*(ll)a[i].r;
}
printf("%lld\n",triplets);
return 0;
}