CODEWITHSUNDEEP
arraysalgorithm
vrume21
vrume21

Reputation: 551

Find if element in array occurs more frequently than some value

I have the problem where given an array, A[1...n] of n (not necessarily distinct) integers, find an algorithm to determine whether any item occurs more than ceiling of n/4 times in A.

It seems that the best-possible worst case time is O(n). I am aware of the majority element algorithm and am wondering if this may be applied to this situation. Please let me know if you have any suggestions for approaching this problem.

Upvotes: 2

Views: 1281

Answers (2)

Saeed Amiri
Saeed Amiri

Reputation: 22555

There are three possibilities for this element(s), either it's a median of array, or is a median of n/2 smallest elements of array or it's a median of n/2 largest elements of array.

In all cases first find the median of array. After that check whether it occurs in at least n/4 elements, if not then divide array into two part of almost same size (they differ in size by at most one element):

  • smaller than equal to median
  • bigger than equal to median

Then find the median of each of these two subarrays and check the number of occurrences of each of them. This is in all O(n). Also in this way you can find all elements with occurrence at least n/4 times.

By the way you can extend this technique to find any element with O(n) time occurrence (e.g n/10000), which works again in O(n).

Upvotes: -2

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

This is only an idea of an algorithm but I believe it should be possible to make it work.

The main trick is as follows. If you look at any four elements and they are all different, you may throw all four away. (If any of the thrown elements had more than 1/4 frequency in the old array, it will in the new array; if none had, none will).

So you go over an array, throwing away tuples of four, and rearranging the rest. For instance, if you have AABC and then DDEF, you rearrange to AADDBCEF and throw BCEF away. I will let you work out the details, it's not hard. In the end you should be left with pairs of identical elements. Then you throw odd-numbered elements away and repeat.

After each run you may be left with 1, 2 or 3 elements with no pair that you cannot throw away. No worry, you can combine the leftovers of two runs such that there are never more than 3 elements in the leftover pile. E.g. if after run 1 you have A,B,C and after run 2 you have A,D,E you leave just A. Remember that elements from the second run count twice, so in effect you have 3"A, which is more than 1/4 of the total of 9. Keep count of each leftover element to track which of them can be thrown away. (You might be able to just always keep the last leftovers, I have not checked that).

In the end you will have just the leftovers. Check each one against the original array.

Upvotes: 5

Related Questions