# Multiple occurrences | Hackerearth practice problem solution

Problem:-

You are given an integer array

$A$

. Your task is to calculate the sum of absolute difference of indices of first and last occurrence for every integer that is present in array

$A$

.

Formally, if element

$x$

occurs

$m$

times in the array at indices

, then the answer for

$x$

will be

${B}_{m}-{B}_{1}$

if array

$B$

is sorted.

You are required to calculate the sum of the answer for every such

$x$

that occurs in the array.

Refer to sample notes and explanations for better understanding.

Input format

• The first line contains an integer
$T$

that denotes the number of test cases.

• The first line of each test case contains an integer
$x$

that denotes the number of elements in the array.

• The second line of each test case contains
$x$

space seperated integers

.

Output format

For each test case, print a single line as described in the problem statement.

Constraints

$1\le T\le 1000$

$1\le N\le 200000$

$1\le {A}_{i}\le 1e9\mathrm{\forall }i\in \left[0,n-1\right]$

The sum of

$N$

over all test cases will not exceed 200000.

Sample Input
`151 2 3 3 2`
Sample Output
`4`
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

The elements which occur in the array are 1,2,3.

Let us consider 1 it has only one occurrence so answer for 1 is 0.

Let us consider 2 it has two occurrence at 2 and 5 so |5-2|=3

Let us consider 3 it has two occurrence at 3 and 4 so |4-3|=1.

So total sum=0+3+1=4.

If there are more than two occurrence we only need to consider the first and last.

Code:-

Here I am going to give you two solution first one is on the basis of C language and second one is on the basis of c++ language which you can submit in c++14 and c++17 also

Solution 1 ( C language):-

#include<stdio.h>
#define MAX 200000
void quickSort(int r[MAX],int z[MAX],int i,int j){
int smaller=i+1,larger=j,swap,pivot,k;
if(i>=j) return;
while(smaller<larger){
if(r[smaller]<=r[i]) smaller++;
else{
if(r[larger]>r[i]) larger–;
else {
swap=r[smaller];
r[smaller]=r[larger];
r[larger]=swap;
swap=z[smaller];
z[smaller]=z[larger];
z[larger]=swap;
}
}
}
if(r[smaller]<=r[i]) pivot=smaller;
else pivot=smaller1;
swap=r[i];
r[i]=r[pivot];
r[pivot]=swap;
swap=z[i];
z[i]=z[pivot];
z[pivot]=swap;
quickSort(r,z,i,pivot1);
quickSort(r,z,pivot+1,j);
}
void main(){
int a[MAX],b[MAX],t,n,i,j,sum,pivot,max,min;
scanf(“%d”,&t);
while(t–){
scanf(“%d”,&n);
for(i=0;i<n;i++){
scanf(“%d”,&a[i]);
b[i]=i;
}
quickSort(a,b,0,n1);
pivot=0;
sum=0;
min=-1;
max=-1;
for(i=0;i<n;i++){
if(a[i]==a[pivot]){
if(min==-1&&max==-1){
min=b[i];
max=b[i];
}else if(b[i]<min) min=b[i];
else if(b[i]>max) max=b[i];
}
if(a[i]!=a[pivot]){
sum+=(maxmin);
pivot=i;
min=b[pivot];
max=b[pivot];
}
}
sum+=(maxmin);
printf(“n%d”,sum);
}
}

Solution 2 ( C++ language):-

This solution is based on the c++ language and you can submit ib c++14 and c++17 also.
In this solution first three lines of the main function is only for the decreasing the time of execution of the program..
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

This is your choice that you want to use this or not but in some cases the code may take more time in execution and that time we need it .

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t–)
{
int n, input; cin>>n;
vector <pair<ll, ll>> valuePair;
for(int i=1; i<=n; i++)
{
cin>>input;
valuePair.push_back(make_pair(input, i));
}
sort(valuePair.begin(), valuePair.end());
ll total=0;
for(int i=0; i<n; i++)
{
if(valuePair[i].first==valuePair[i1].first)
{
total += valuePair[i].second valuePair[i1].second;
}
}
cout<<total<<endl;
}
return 0;
}

Recommended Post:-