PROBLEM LINK
Author: Vikesh Tiwari
Tester : Vikesh Tiwari
Editorialist: Vikesh Tiwari
DIFFICULTY:
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++.
Read more about Set in C++ here.
- 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;
}