Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
  • Work with US
Programmingoneonone
Programmingoneonone

HackerEarth HP and Splitting of Array problem solution

YASH PAL, 31 July 2024
In this HackerEarth HP and Splitting of Array problem solution, HP recently started learning about a property called inversion count. An inversion count of an array indicates how far from (or close to) being sorted the array is. If the array is already sorted, the inversion count is 0; if it’s sorted in reverse order, the inversion count is maximal.
Formally speaking, two elements  and  form an inversion if  and . The inversion count is the number of pairs of indices  such that  and  form an inversion.
You are given an array A with size N. Let’s denote an i-rotation of this array as the array formed by removing the first i elements from the array and adding (appending) them to the end of the array in the same order. HP wants to know the inversion counts of i-rotations of array A. Compute this inversion count for each i (1 <= i <= N).
HackerEarth HP and Splitting of Array problem solution

HackerEarth HP and Splitting of Array problem solution.

#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define nax 1000005

using namespace std;

long long ftree1[nax], ftree2[nax];
long long arr[nax];
long long temp[nax];
long long l[nax],r[nax];


void update(ll idx ,ll *ftree)
{
while(idx<nax)
{

ftree[idx]+=1;
idx += (idx &(-idx));
}
}
ll query(ll idx,ll *ftree)
{
//cout<<idx<<"n";

ll sum =0;
while(idx!=0)
{


sum+=ftree[idx];
idx -= (idx &(-idx));

}
return sum;
}

set<int> s;

int main()
{

ll t,n,q,x;
cin>>t;
assert(t>=1 && t<=10);
while(t--){


cin>>n;
assert(n>=1 && n<=100000);

memset(ftree1,0,sizeof(ftree1));
memset(ftree2,0,sizeof(ftree2));

for(int i=0;i<n;i++)
{
cin>>arr[i];
assert(arr[i]>=1 && arr[i]<=1000000);

if(!i)
l[i]=(query(nax-1,ftree1)-query(arr[i],ftree1));
else
{
l[i]=l[i-1]+(query(nax-2,ftree1)-query(arr[i],ftree1));
}

update(arr[i],ftree1);

}

r[n] = 0;
for(int i=n-1;i>=0;i--)
{
if(i==n-1)
r[i]=query(arr[i],ftree2);
else
{
r[i]=r[i+1]+query(arr[i],ftree2);
}
update(arr[i],ftree2);

}





for(int i=1;i<=n;i++)
{
int x = i-1;

ll total = (n-x-1)*(x+1);
ll ans;
ans = 2*l[x]+2*r[x+1] + total - r[0];


cout<<ans<<" ";

}
cout<<"n";

}

}

Second solution

#include <bits/stdc++.h>
#define MAX 1000005
#define lli long long

using namespace std;

int A[MAX];
lli BIT[MAX];
lli ans[MAX];

void update(int idx, int val)
{
while ( idx <= MAX - 4 ) {
BIT[idx] += val;
idx += (idx & (-idx));
}
}

int query(int idx)
{
int ret = 0;
while ( idx > 0 ) {
ret += BIT[idx];
idx -= (idx & (-idx));
}
return ret;
}
int main()
{
int n, q, x,t;
cin>>t;
while(t--){

lli inv = 0;
cin >> n ;
memset(BIT,0,sizeof(BIT));



for ( int i = 1; i <= n; i++ ) {
cin >> A[i];
assert(A[i] >= 1 && A[i] <= 1000000);
}

for ( int i = n; i >= 1; i-- ) {
inv += query(A[i] - 1);
update(A[i], 1);
}

for ( int i = 1; i <= n; i++ ) {
inv -= query(A[i] - 1);
inv += query(MAX - 5) - query(A[i]);
ans[i] = inv;
}


for(int i=1;i<=n;i++) {


cout << ans[i] << " ";
}
cout<<endl;
}


return 0;
}
coding problems solutions

Post navigation

Previous post
Next post

Related website

The Computer Science

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes