Distinct Enemies

Easy
0/40
Average time to solve is 20m
profile
Contributed by
22 upvotes
Asked in company
Walmart

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5
2 3 5 3 2
5
2 2 2 2 3
Sample Output 1 :
3
2
Explanation For Sample Input 1 :
Test Case 1:
For the first test case, the given array is { 2, 3, 5, 3, 2 } so we return ‘3’ as we can say ‘3’ distinct values are present in the array i.e { 2, 3, 5}.

Test Case 2:
For this test case, the given array is { 2, 2, 2, 2, 3 } so we return ‘2’ as we can say ‘2’ distinct values are present in the array i.e { 2, 3}.
Sample Input 2 :
2
2
5 5
5
1 6 7 9 4
Sample Output 2 :
1
5
Hint

Can you think of traversing the array and try to make elements of the given array ‘0’.

Approaches (3)
Brute 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’.
Time Complexity

O(N ^ 2), where ‘N’ represents the size of the given array.

 

As we are running two nested loops each loop takes O(N) time so overall complexity becomes O(N ^ 2).

Space Complexity

O(1).

 

As we are using constant space.

Code Solution
(100% EXP penalty)
Distinct Enemies
Full screen
Console