Header Ads Widget

Multiple occurrences | Hackerearth practice problem solution


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 B1, B2, B3, ...,Bm, then the answer for x will be BmB1 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 A1, A2, A3, ...,An.

Output format

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





The sum of N over all test cases will not exceed 200000.

Sample Input
1 2 3 3 2
Sample Output
Time Limit: 1
Memory Limit: 256
Source Limit:

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.


  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):-

#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;
        if(r[smaller]<=r[i]) smaller++;
            if(r[larger]>r[i]) larger--;
            else {
    if(r[smaller]<=r[i]) pivot=smaller;
    else pivot=smaller-1;
void main(){
    int a[MAX],b[MAX],t,n,i,j,sum,pivot,max,min;
                }else if(b[i]<min) min=b[i];
                else if(b[i]>max) max=b[i];

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..

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 .

using namespace std;
#define ll long long
int main()
    int t;
        int n, input; cin>>n;
        vector <pair<ll, ll>> valuePair;
        for(int i=1; i<=n; i++)
            valuePair.push_back(make_pair(input, i));
        sort(valuePair.begin(), valuePair.end());
        ll total=0;
        for(int i=0; i<n; i++)
                total += valuePair[i].second - valuePair[i-1].second;
    return 0;

Recommended Post:-

Post a Comment