# SPIT04- Editorial

Practice

Contest

Author: Vikesh Tiwari

Tester : Vikesh Tiwari

Editorialist: Vikesh Tiwari

Easy

## PREREQUISITES:

data Structures,array,set

## PROBLEM

You’re given an array a, consisting of integers . There are m integers

For each integer Find number of distinct elements among

## EXPLANATION

There can be two different Approaches to the Problem.

As We need to Find, Distinct Elements from the given number to Upto ‘N’. We can use ‘set’ in C++.

• Insert Element in the Set.
• Create another array B[] which will store size of set after each iteration.

Now read integer ‘m’ and just print B[m].

## COMPLEXITY :

O(N)

C++ Code:

``````#include<iostream>
#include<set>
using namespace std;
int n,m,i,a[100005],b[100005],k;
set <int> s;
main()
{
cin>>n>>m;
for(i=0;i<n;i++)
cin>>a[i];

for(i=n-1;i>=0;i--){
s.insert(a[i]);
b[i+1]=s.size();
}

for(i=0;i<m;i++){
cin>>k;
cout<<b[k]<<endl;
}
}
``````

Approach 2

This can be solved without using sets, for this we need three arrays.

• array A[] will store elements.
• array B[] will store number number of times, an element is repeated.
• array C[] will count of distinct elements.

Check C++ Code Below

COMPLEXITY: O(N)

Code:

``````#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<set>
#include<algorithm>
#define LL long long
#define S system("pause")
using namespace std;
LL  n,i,j,k,q,m,a[200000],d,b[200000],c[200000],l;
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
for(i=n;i>=1;i--)
{
b[a[i]]++;
if(b[a[i]]==1)
{
q++;
}
c[i]=q;
}
for(i=1;i<=m;i++)
{
cin>>l;
cout<<c[l]<<endl;
}
return 0;
}
``````

@vicky002 Why do we pick magic numbers 100005 and 200000 for array sizes?