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 $B_1,B_2,B_3,...,B_m$, 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 $A_1,A_2,A_3,...,A_n$.

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 [0,n-1]$

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

Sample Input

1
5
1 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=smaller-1;

    swap=r[i];

    r[i]=r[pivot];

    r[pivot]=swap;

    swap=z[i];

    z[i]=z[pivot];

    z[pivot]=swap;

    quickSort(r,z,i,pivot-1);

    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,n-1);

        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+=(max-min);

                pivot=i;

                min=b[pivot];

                max=b[pivot];

            }

        }

        sum+=(max-min);

        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[i-1].first)

            {

                total += valuePair[i].second - valuePair[i-1].second;

            }

        }

        cout<<total<<endl;

    }

    return 0;

}

Recommended Post:-

• Hackerearth Problems:-
  
  
  • Very Cool numbers | Hacker earth solution
  • Birthday party | Hacker earth solution
  • Most frequent | hacker earth problem solution
  • program to find symetric difference of two sets
  •  cost of balloons | Hacker earth problem solution
  • Chacha o chacha | hacker earth problem solution
  • jadu and dna | hacker earth solution
  • Bricks game | hacker earth problem
  • Anti-Palindrome strings | hacker earth solution
  • connected components in the graph | hacker earth data structure
  • odd one out || hacker earth problem solution
  • Minimum addition | Hackerearth Practice problem
    
  • The magical mountain | Hackerearth Practice problem
    
  • The first overtake | Hackerearth Practice problem
    
  Data structure:-
  
  •   Program to find cycle in the graph
  • Implementation of singly link list
  • Implementation of queue by using link list
  • Algorithm of quick sort
  • stack by using link list
  • program to find preorder post order and inorder of the binary search tree
  • Minimum weight of spanning tree
    
  • Preorder, inorder and post order traversal of the tree
    
  Key points:-
  • How to set limit in the floating value in python
    
  • What is boolean data type
  • How to print any character without using format specifier

  Must check this:-
  

  • PPS lab all the problems of 1st year