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 

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.

Constraints

1T1000

1N200000

1Ai1e9i[0,n1]

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



Leave a Reply

Your email address will not be published.