Alex Rivera | Logout

number which appears more than n/3 times in an array

Asked 2013-02-19T10:52:09.027
14

I have read this problem Find the most common entry in an array

and the answer from jon skeet is just mind blowing .. :)

Now I am trying to solve this problem find an element which occurs more than n/3 times in an array ..

I am pretty sure that we cannot apply the same method because there can be 2 such elements which will occur more than n/3 times and that gives false alarm of the count ..so is there any way we can tweak around jon skeet's answer to work for this ..?

Or is there any solution that will run in linear time ?

algorithm
Edit
Report

1 Answer

28

Jan Dvorak's answer is probably best:

  • Start with two empty candidate slots and two counters set to 0.
  • for each item:
    • if it is equal to either candidate, increment the corresponding count
    • else if there is an empty slot (i.e. a slot with count 0), put it in that slot and set the count to 1
    • else reduce both counters by 1

At the end, make a second pass over the array to check whether the candidates really do have the required count. This isn't allowed by the question you link to but I don't see how to avoid it for this modified version. If there is a value that occurs more than n/3 times then it will be in a slot, but you don't know which one it is.

If this modified version of the question guaranteed that there were two values with more than n/3 elements (in general, k-1 values with more than n/k) then we wouldn't need the second pass. But when the original question has k=2 and 1 guaranteed majority there's no way to know whether we "should" generalize it as guaranteeing 1 such element or guaranteeing k-1. The stronger the guarantee, the easier the problem.

answered 2013-02-19T11:14:41.740

Your Answer