Last Updated: 8 Jan, 2021
Dominant Number
Moderate
Asked in company
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
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
Approaches
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.
In this approach, we will store the count of each element again, but this time we will store it in a hashmap because it will reduce the calculation which inner loop was doing again, so we will declare a hashmap ‘COUNT’ that will store element as key and count of that element as value. Now let’s discuss the algorithm-
- Declare the hashmap<Integer, Integer> COUNT and initialize the ANSWER=0;
- Iterate the array by running a loop from index I=0 till the end of the array
- And check for each element, now. If the element is already present in the hashmap COUNT, then update the value of that element by incrementing one to its value, i.e., COUNT.PUT(ARR[I], COUNT.GET(ARR[I]) + 1).
- Now check for that element if it has a value greater than N/3, i.e., COUNT.GET(ARR[I]) > N/3, then just return from that point and return the key from there, i.e., ANSWER= ARR[I] and return ANSWER.
- Else if the element is not present in the hashmap, then put the key-value pair in the hashmap that is COUNT.PUT(ARR[I],1);
- Finally, if the loop ends, then return -1 because no such element is present in the array.
In this approach, we will consider two elements and check for these two elements that they are forming the dominant number, and if one of the candidates is dominant, then return else, we will update these two elements for further iterations.
- Initialize two variables that will store the values for the candidates for dominant element DOMONE and DOMTWO; both initialized to maximum and minimum integers.
- Initialize two more variables as COUNTDOMONE AND COUNTDOMTWO to zero for storing the count for the first and second candidate to be the dominant number.
- Now start running the loop from index I=0 till the end of the array; basically, in this algorithm, we consider that if there is a repetition of the element in the array that is chosen as the candidate of the dominant number, we increase the count for that dominant candidate else we decrease the count of both the candidates.
- We add one more case that if the count of any one of the candidates becomes zero, we update the candidate as the current element in the iteration.
- Now finally, we will cross-check that whether the chosen candidates are actually the dominant number or not by checking the counts of both candidates in the array and if any one of the counts becomes greater than N/3.
- Then return that candidate else; we will return -1 as the answer.
Similar problems