Last Updated: 27 Apr, 2021

Distinct Enemies

Easy

Asked in company

Solve now

Problem statement

Ninja has somehow got the list of enemies and their strength. Now ninja wants to make a plan according to enemies on the basis of their strength. But ninja wants to first count the distinct type of enemies as some of them have the same strength.

So help our ninja in counting the distinct type of enemies from the given array where ‘ARR[i]’ represents the strength of the i-th enemy.

Note :

Two enemies are distinct if their strengths are different.

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a single integer ‘N’ denoting the size of the ‘ARR’ array.

The next line contains ‘N’ space-separated integers denoting the values of elements of the ‘ARR’ array.

Output Format :

For each test case, print a single line containing the distinct elements in an array.

The output of each test case will be printed in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 5000
0 <= ARR[i] < 10 ^ 6

Where ‘ARR[i]’ represents the elements of the array.

Time Limit: 1 sec

Solve now

Approaches

01 Approach

The idea here is to use the brute force approach and for each element, we check for all the previous elements if we find the same element we break from the loop, and if after one loop both ‘i’ and ‘j’ becomes equal we increase the ‘ans’ as we can say a different element is present.

Algorithm:

Firstly declare a variable name ‘ans’ for storing the final count and initialize it with ‘1’.
Run a loop where ‘i’ starts from ‘1’ upto the size of the array.
- Run another loop where ‘j’ starts from ‘0’ and run upto the value less than ‘i’.
  - Now check :
    - If( ‘ARR[i] == ARR[j]’ )
      - Break.
- If ( i == j)
  - Increment ‘ans’ by 1 i.e. do ‘ans++’.
Return the ‘ans’.

Solve now

02 Approach

The idea here is to sort the array then we can simply traverse the array and check if the next element is different from the current element we can increase the ‘ans’ .

Algorithm:

Firstly declare a variable name ‘ans’ for storing the final count and initialize it with ‘1’.
Now sort the array.
Run a loop where ‘i’ starts from ‘0’ upto the size of the array.
- Now we check :
  - If ( ‘ARR[i] != ARR[i + 1 ]
    - Increment ‘ans’ by 1 i.e. do ‘ans++’.
Return ‘ans’.

Solve now

03 Approach

The idea here is to use the hash set as it maintains a unique entry for each element and whenever we encounter any element we first check in our hash set if it is already present we continue else we push it into our hash set and increase the ‘ans’.

Algorithm:

Firstly declare a variable name ‘ans’ for storing the final count and initialize it with ‘0’ and a hashmap 'hashSet'.
Run a loop where ‘i’ starts from ‘0’ upto the size of the array.
- Now we check :
  - If ‘ARR[i] does not exist in 'hashSet'.
    - Increment ‘ans’ by 1 i.e. do ‘ans++’.
    - Insert ‘ARR[i]’ into 'hashSet'.
Return ‘ans’.

Solve now