You are not logged in. Please login at www.codechef.com to post your questions!

×

SPIT04- Editorial

PROBLEM LINK

Practice
Contest

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

asked 23 Apr '15, 07:56

vicky002's gravatar image

1★vicky002 ♦♦
2561314
accept rate: 27%

edited 23 Apr '15, 17:23

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 23 Mar '17, 09:57

janani__a's gravatar image

0★janani__a
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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