Problem

Submissions

Hints & solutions

Discuss

Dominant Number

Moderate

0/80

Average time to solve is 15m

5 upvotes

Asked in company

Problem statement

You are given an array of integers 'ARR' of size N. Your task is to find the dominant number in the array.

A dominant number in an array is an integer that occurs more than N/3 times in the array, where N is the array’s length.

Note:

1. There will be only one such element (if it exists).
2. If there is no such element in the array, return -1.

For Example:

If the given array ARR = {3,3,3,1,5,6,3} we can see that here 3 occurs 4 times in the array, which is greater than 7/3(N/3), so the dominant number here is 3.

Note:

Try to solve the problem in linear time complexity

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.
The next ‘2*T’ lines represent the ‘T’ test cases.

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

The second line of each test case contains N space-separated integers denoting the array elements at various indices.

Output format :

For each test case, return a single integer representing the dominant number in the array.

Note:

You don’t have to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N<= 10^4
0 ≤ ARR[I] ≤ 10^5

Time Limit: 1 sec

Sample Input 1 :

3
6
3 1 1 8 1 2
3
1 2 4
4
3 2 1 3

Sample Output 1 :

1
-1
3

Explanation of The Sample Input 1:

For the first test case:
The given array is {3,1,1,8,1,2} we can see that 3 occurred three times in the array, which is greater than 6/3, so the dominant number will be 3. 

For the second test case:
The given array is {1,2,4} we can see that no number here is repeated more than once, so the answer here will be -1.

For the third test case
The given array is {3,2,1,3} we can see that  3 occurred two times in the array, which is greater than 4/3, so the dominant number will be 3.

Sample Input 2 :

3
4
4 4 4 1
7
5 6 6 4 3 2 6
8
1 9 8 4 5 5 5 5

Sample Output 2 :

4
6
5

Hint 1

Hint 2

Hint 3

Try to think about how you will keep the count of each element.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

The idea is to keep the count for each element and check for each element if the count for that element is greater than N/3 or not. This can be done by comparing each element with all the rest of the elements in the array.

Initialize the ANSWER = 0 and FLAG = FALSE for storing the element that is dominant and FLAG for checking if there exists the dominant element or not.
Now run a loop from index I = 0 till the end of the array.
Initialize COUNT =0 for storing the count for each element
Inside this loop, run one more loop from index J=0 till the end of the array because we have to compare each element with all the rest of the elements.
Inside the second compare ARR[I]==ARR[J] and if it is true, increment the count.
Now, after this loop, check if this count is greater than N/3, i.e., if(COUNT > N/3), then update ANSWER and ARR[I] and then update FLAG = TRUE break the loop.
Now check if the FLAG value is true; that means there exists a dominant element, so return ANSWER.
Else return -1.

Time Complexity

O(N^2), Where ‘N’ denotes the number of elements in the Array

because we are using two nested loops.

Space Complexity

O(1), We are using constant space.

(100% EXP penalty)

Dominant Number

Console