6

I was asked in an interview to give an O(n) algorithm to print an element that appears more than n/2 times in an array, if there is such an element. n is the size of the array. I don't have any clue on how to do this. Can anyone help?

softwarematter
  • 28,015
  • 64
  • 169
  • 263

3 Answers3

15

It's the Boyer's Voting algorithm.

It's also O(1) in space!.

Edit

For those complaining about the site color scheme (like me) ... here is the original paper.

Dr. belisarius
  • 60,527
  • 15
  • 115
  • 190
  • 3
    The colour scheme on that link is horrible. – Anon. Dec 21 '10 at 03:40
  • 2
    Here's some more info: http://stackoverflow.com/questions/780937/linear-time-voting-algorithm-i-dont-get-it – chrisaycock Dec 21 '10 at 03:43
  • 1
    Nice read. Took me a minute to find the subtle logic which avoids maintaining independent counts: "..._increment or decrement the counter_ according to whether e is the current candidate..." –  Dec 21 '10 at 03:55
  • @pst Boyer has several of those subtleties in his works. Look for example his string matching algorithm. A jewel! http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm – Dr. belisarius Dec 21 '10 at 03:58
  • 1
    Thanks! @chrisaycock that link was informative. I was having similar doubt. – softwarematter Dec 21 '10 at 03:59
0

In psuedocode:

int n = array.length
Hash<elementType,int> hash
foreach element in array
    hash[element] += 1
foreach entry in hash
    if entry.value > n/2
        print entry.key
        break
Samuel
  • 16,923
  • 6
  • 62
  • 75
  • Wouldn't this be considered O(2n) ? – Eric Fortin Dec 21 '10 at 03:39
  • 1
    @Eric This would be `O(n+m)`. By the way, there is no such thing as `O(2n)` as big-O doesn't use constant coefficients; in such a case it's just `O(n)`. – chrisaycock Dec 21 '10 at 03:41
  • @chrisaycock. Let `m` be the number of entries in `hash`, and `n` be the number of elements in `array`. `m <= n` so assuming no hash collisions, this algorithm does indeed take `O(n)` time. (If we allow for hash collisions, it takes `O(n^2)` time worst case.) – Ken Bloom Dec 21 '10 at 03:54
  • @chrisaycock - There is such a thing as O(2n)... its just the same as O(n). It is still a valid statement. – Chris Hopman Dec 21 '10 at 04:34
0

It's also the median value, which takes O(n) to find using the median-of-medians algorithm. In C++ you can do this in one line:

std::nth_element(begin, begin + n/2, begin + n)
Inverse
  • 4,408
  • 2
  • 26
  • 35
  • Note though that `std::nth_element` is only required to be expected O(n) and so likely does not use the median-of-medians algorithm. The quick-sort like selection tends to be better in practice than m-of-m. – Chris Hopman Dec 21 '10 at 04:37