James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1431 , trackbacks - 0

My Links

News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Archives

.NET

CSharp

Little Wonders

Little Wonders

vNext

Little Puzzlers–The Majority Element

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.

Print | posted on Tuesday, July 7, 2015 11:19 AM |

Powered by: