# 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

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

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:
# 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);
}
}

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];
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];
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 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)
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)
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;
}```