Introduction
Finding an element in a sorted array whose frequency is greater than or equal to n/2 is an array searching problem. It is one of the very basic problems that have many approaches. That’s why it had been asked in many interviews. It had been asked in the Microsoft, Google, Amazon, and Yahoo interview round for the role of software engineers/developers. Alongside it is one of those problems that checks an individual's critical thinking by analyzing the most fundamental approach of the programmer.
In this article, we are going to discuss two methods to solve this problem find element in a sorted array whose frequency is greater than or equal to n/2; the first is the brute force or naive approach, and the second is by using Boyer-Moore Majority Vote Algorithm.
Also see, Array Implementation of Queue and Rabin Karp Algorithm
Problem Statement
Find an element in a sorted array whose frequency is greater than or equal to n/2, in here we are given a sorted array A[] of n elements. We need to find and return the number that appears more than n/2 times.
Sample Examples
Example 1:
Input: A[] =
Output:
3Explanation: In the above example, the total number of elements in the array is 8, and the element which is appearing more than n/2 or 8/2=4 times is 3. That’s why the output is 3.
Example 2:
Input: A[] =
Output:
8Explanation: In the above example, the total number of elements in the array is 10, and the element which is appearing more than n/2 or 10/2=5 times is 8. That’s why the output is 8.
Example 3:
Input: A[] =
Output:
5Explanation: In the above example, the total number of elements in the array is 6, and the element which is appearing more than n/2 or 6/2=3 times is 5. That’s why the output is 5.
Brute Force Approach (using nested loops)
For this problem, a simple brute force approach would be to use nested loops and count the frequency of each element. When we reach an element with a frequency greater than n/2, we have found our majority element.
Pseudocode
for i = 0 to n-2
int count = 1
for j = i+1 to n-1
if A[i] is equal to A[j]
count = count + 1
if count > n/2
return A[i]Implementation
#include <iostream>
using namespace std;
int findMajorityElement(int A[], int n)
{
for (int i = 0;i< n-2;i++ )
{ int count = 1;
for ( int j = i+1;j< n-1;j++ )
{
if ( A[i] == A[j] )
count = count + 1;
}
if ( count > n/2 )
return A[i];
}
return -1;
}
int main()
{
int arr[] = {1,3,3,3,3,3,5,9};
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMajorityElement(arr, n);
return 0;
}
Output
3Time complexity
The time complexity of this approach is O(N^2). Since we are using nested loops and iterating each loop N time.
Space complexity
The space complexity of this approach is O(1). Since we are not using any extra space.
305+ registered