Little Puzzlers–The Majority Element

July 7, 2015 · 1 min read

I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.

The Problem

The problem is simple to state, but not immediately apparent how to solve efficiently.

Given a list of numbers, determine the number in the majority – that is, find the number that occurs over 50% of the time (for a list of size n that’s ⌊n/2⌋ times).

For example, in this sequence:

1, 2, 1, 4, 2, 1, 1, 5, 1, 1

The majority element is 1 occuring 6 times in a sequence of length 10.

However, in this sequence:

1, 2, 5, 4, 2, 1, 5, 5, 1, 1

There is no majority element since no element occurs > 50% of the time.

Hints

Please note that it is not enough to say which element occurs the most often, you have to also determine it’s the majority as well.

Spoiler Alert!

Fair Warning: there may be discussion of the problem and potential solutions posted in the comments below. Read at your own risk.

This article is part of the GWB Archives. Original Author: James Michael Hare

New on Geeks with Blogs

  • We Won The One Award I Actually Care About

    Full Scale made the Inc. 5000 for the fifth year straight, the 12th listing across my three companies. Here is why the one award you cannot buy is worth stopping for.

  • Your Customers Build the Features Now

    I let a tool I liked sit dead for a year rather than build the features I wanted. An MCP server meant I never had to, and your customers can do the same to your product.

  • Get the Size of a Directory in Linux the Easy Way

    du -sh for the quick answer, ncdu for the cleanup, df for the disk itself: every command for checking directory size in Linux, plus why du and df never agree.

  • Vim Search and Replace: The Ultimate Guide

    One :%s command replaces every match in a file before a find dialog would even open. The Vim substitute patterns worth the muscle memory: flags, ranges, capture groups, and multi-file edits.