Find popular element in an array

Find popular element in an array

Given a sorted array of integers, find a "popular" element i.e. one which occurs more than n/4 times. If no such element exist (which occurs more than n/4 times) then print error. For example: If Input array has 8 elements as below {1, 3, 3, 3, 4, 6, 9, 10} Then 3 is the popular element that comes three times. Solution: Brute Force – O(n) The brute force method will traverse the array linearly and for each element 'i' it will check if(arr[i] == arr[i+n/4]) // arr[i] is popular elment else // Continue with other element It will take O(n) time to find the popular element using above algorithm. Since the array is sorted, we can take advantage of some binary search type logic to reduce the time taken to lg(n). lg(n) time algorithm This is a two part algorithm, first we find the candidate and then we check whether any of the candidate is a popular element. If we divide the array in 4 parts, then popular element will be first element of one of the four parts. So,

Read full article from Find popular element in an array