 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,b,k;
set <int> s;
main()
{
cin>>n>>m;
for(i=0;i<n;i++)
cin>>a*;

for(i=n-1;i>=0;i--){
s.insert(a*);
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,d,b,c,l;
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++)
{
cin>>a*;
}
for(i=n;i>=1;i--)
{
b[a*]++;
if(b[a*]==1)
{
q++;
}
c*=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?