×

# SPIT04- Editorial

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++. 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;
}


2561314
accept rate: 27%

19.8k350498541

 0 @vicky002 Why do we pick magic numbers 100005 and 200000 for array sizes? answered 23 Mar '17, 09:57 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,851
×2,211
×1,409
×849

question asked: 23 Apr '15, 07:56

question was seen: 1,399 times

last updated: 23 Mar '17, 10:27