James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 164 , comments - 1434 , 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

Article Categories

Archives

Post Categories

Image Galleries

.NET

CSharp

Little Wonders

Little Wonders

vNext
<< Summer Vacation & 2015 Visual C# MVP Award | Home | Solution to Little Puzzlers–Find the Majority Element >>

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 |

Feedback

Gravatar

# re: Little Puzzlers–The Majority Element

C# with an Extension Method.

var oneIsTheMajorityElement = new int[] { 1, 2, 1, 4, 2, 1, 1, 5, 1, 1 };
var noMajorityElement = new int[] { 1, 2, 5, 4, 2, 1, 5, 5, 1, 1 };
Console.WriteLine(oneIsTheMajorityElement.HasMajorityElement());
//returns { True, 1, 6 };

Console.WriteLine(noMajorityElement.HasMajorityElement());
//returns { False, 1, 4 };


public static Tuple<bool, int, int> HasMajorityElement(this int[] array)
{
return array
.GroupBy(item => item)
.OrderByDescending(g => g.Count())
.Select(g =>
new Tuple<bool, int, int>(
(((double)g.Count() / (double)array.Length) > .5),
g.Key,
g.Count()))
.First();
}
7/7/2015 2:04 PM | Scott G.
Gravatar

# re: Little Puzzlers–The Majority Element

var l = new List<int>{1, 2, 1, 4, 2, 1, 1, 5, 1, 1};
var d = new Dictionary<int, int>();

l.ForEach(x =>
{
if (d.ContainsKey(x))
{
d[x]++;
if (d[x] > l.Count()/2)
{
Console.WriteLine(x + d[x]);
}
return;
}
d.Add(x, 1);
});
7/8/2015 1:23 AM | Frank
Gravatar

# re: Little Puzzlers–The Majority Element

In F#, fairly brute-force

let majority (s : int seq) =
Seq.groupBy id s
|> Seq.map (fun (a,b) -> (a, Seq.length b))
|> Seq.sortBy snd // a plurality value is last, now
|> Seq.fold (fun (a,(b,c)) (x,y) -> (x, (y, c+y))) (0, (0,0))
|> Seq.singleton // lift into a monad
|> Seq.tryFind (fun (a,(b,c)) -> b+b > c)
|> Option.map fst
;;
7/8/2015 8:04 AM | Mr. Tines
Gravatar

# re: Little Puzzlers–The Majority Element

Assuming that numbers in sequence > 0

public static int Majority(ICollection<int> seq)
{
var seqLength = seq.Count;

var m = seq
.GroupBy(i => i)
.Select(g => new
{
num = g.Key,
freq = g.Count()
})
.FirstOrDefault(g => seqLength / g.freq < 2);

return m != null ? m.num : -1;
}
7/8/2015 8:59 AM | Leon Boshuizen
Gravatar

# re: Little Puzzlers–The Majority Element

Fairly naive approach... could probably be improved to enumerate the input only once.

public static class Extensions
{

public class MajorityInfo<T>
{
public T Value { get; private set; }
public int Count { get; set; }
public double Percentage { get; set; }

public MajorityInfo(T value, int count, double percentage)
{
Value = value;
Count = count;
Percentage = percentage;
}
}

public static MajorityInfo<T> GetMajority<T>(this IEnumerable<T> source)
{
var list = source as IList<T> ?? source.ToList();
var grouped =
list.GroupBy(x => x)
.Select(g => new {
Value = g.Key,
Count = g.Count()
}).ToList();
long target = list.Count / 2;
var majGroup = grouped.FirstOrDefault(g => g.Count > target);
if (majGroup == null)
return null;
return new MajorityInfo<T>(majGroup.Value, majGroup.Count, majGroup.Count * 100.0 / list.Count);
}
}
7/8/2015 9:45 AM | Thomas Levesque
Gravatar

# re: Little Puzzlers–The Majority Element

A lot of interesting LINQ solutions. I definitely appreciate the elegance. That said, keep in mind that a lot of times when you go for a programming interview, they'll want you to consider what will happen if the number of elements is exceedingly large and how that would affect your decision to use certain algorithms and data structures.

Thus, consider how (or if) you can find the majority element in O(n) time. Then, if you are really wanting to push yourself, how can you do it in O(n) time and O(1) space.
7/8/2015 9:59 AM | James Michael Hare
Gravatar

# re: Little Puzzlers–The Majority Element

var nums = new[] {1, 2, 1, 4, 2, 1, 1, 5, 1, 1};

var majority = nums.GroupBy(n=>n)
.Where(n=>n.Count()>=nums.Length/2)
.OrderByDescending (n => n.Count())
.FirstOrDefault();

Console.WriteLine(majority.Any() ? String.Format("Majority element is {0} with count {1} out of {2} elements.", majority.First(), majority.Count(), nums.Length): "No majority element");
7/8/2015 11:12 AM | Brian Hartung
Gravatar

# re: Little Puzzlers–The Majority Element

(oops, should be strictly >Length/2, not >=).
7/8/2015 11:26 AM | Brian Hartung
Gravatar

# re: Little Puzzlers–The Majority Element

Sigh. Repost of shame:

var nums = new[] {1, 2, 1, 4, 2, 1, 1, 5, 1, 1};

var majority = nums.GroupBy(n=>n)
.Where(n=>n.Count()>nums.Length/2)
.OrderByDescending (n => n.Count())
.FirstOrDefault();

Console.WriteLine(majority!=null ? String.Format("Majority element is {0} with count {1} out of {2} elements.", majority.First(), majority.Count(), nums.Length): "No majority element");
7/8/2015 11:32 AM | Brian Hartung
Gravatar

# re: Little Puzzlers–The Majority Element

I can get O(nlogn) with O(1) storage by sorting the list and then counting the # of times the middle element appears in the array to see if it's > length/2.

I'm wracking my brains trying to find an O(n) solution with O(1) storage though.
7/8/2015 1:59 PM | Danny
Gravatar

# re: Little Puzzlers–The Majority Element

I think I've got it. If a number is in the majority, then it must also be the longest run of numbers in the list, if you treat the list like it's circular.

Example: 1,2,1,2,1 <- longest run is 1,1, because of the 1's at the start and end of the list.

int longestRunLength = 0;
int longestRunValue = list[0];
int currentRunValue = list[0];
int currentRunLength = 1;

bool isInCount = false;
int i = 1;

while (i < list.Length || isInCount) {
if (list[i - 1] == list[i]) { currentRunLength++; isInCount = true; }
else { currentRunValue = list[i]; isInCount = false; }

if (currentRunLength > longestRunLength) { longestRunLength = currentRunLength; longestRunValue = currentRunValue; }
i++;
}

int majorityCount = 0;
for (int j = 0; j < list.Length; j++) {
if (list[j] == longestRunValue) { majorityCount++; }
}

return majorityCount > list.Length / 2 ? longestRunValue : null;
7/8/2015 2:29 PM | Danny
Gravatar

# re: Little Puzzlers–The Majority Element

In the first whileloop, you have to use i%list.Length, to avoid the out of bounds exception (my bad).

Example:
list[i%list.Length - 1] == list[i%list.Length]
7/8/2015 2:31 PM | Danny
Gravatar

# re: Little Puzzlers–The Majority Element

My core assumption was not correct. A number can be in the majority and not have the longest run.

Counter example: 1,2,2,2,1,1,2,1,1,2,1
7/8/2015 6:31 PM | Danny
Gravatar

# re: Little Puzzlers–The Majority Element

In Clojure

(defn majority [xs]
(if (empty? xs)
xs
(let [majority-size (quot (count xs) 2)
majority-groups (->> xs
frequencies
(filter #(<= majority-size (val %)))
(sort-by val >)
(group-by val))]
(if (empty? majority-groups)
[]
(->> majority-groups first val (map key))
))))

See also gist: https://gist.github.com/MikeMKH/58559a23852d2ba6a5b7
7/9/2015 7:21 AM | Mike Harris
Gravatar

# re: Little Puzzlers–The Majority Element

Can we assume the length in known in advance (as a O(1) operation) ?
7/9/2015 12:27 PM | James Curran
Gravatar

# re: Little Puzzlers–The Majority Element

And what is the range for the values that may appear in the list?
7/9/2015 12:39 PM | James Curran
Gravatar

# re: Little Puzzlers–The Majority Element

Assuming the answers "Yes" and "integers 0 to 9" for the above questions, here is my solution: https://gist.github.com/47f56951bb7ea7f318cc

It's O(N), with an "early out".

If the answer is something else for the latter question, I'd have to make the "count" array a dictionary (and use a different "no majority item found" sentinel), by otherwise the code would be the same. (If the answer to the formar question is "no", this won't work at all)
7/9/2015 1:05 PM | James Curran
Gravatar

# re: Little Puzzlers–The Majority Element

static int? FindMajorityElement( int[] numbers )
{
// we'll just blindy pick a candidate and start counting it
int currentCandidate = numbers[0];
int currentCount = 1;

for (int i = 1; i < numbers.Length; i++)
{

// if we see candidate again, count it
if ( currentCandidate == numbers[i] )
{
currentCount++;
}
else // otherwise, decrement the count
{
currentCount--;
}

// count hit zero
// we know that the previous portion of array has no majority
// it has a candidate and an equal number of unknowns
// therefore forget about it, pick a new one
if ( currentCount == 0 )
{
currentCandidate = numbers[i];
currentCount = 1;
}
}

// the final candidate COULD be the majority. but we need to check
currentCount = 0;
for (int i = 0; i < numbers.Length; i++)
{
if ( currentCandidate == numbers[i] )
{
currentCount++;
}
}

if ( currentCount > numbers.Length / 2 )
{
return currentCandidate;
}

return null;
}
7/9/2015 10:48 PM | Rob
Gravatar

# re: Little Puzzlers–The Majority Element

^solves in two array traverses O(n) and uses O(1) memory
7/9/2015 10:50 PM | Rob
Gravatar

# re: Little Puzzlers–The Majority Element

Also, these puzzles have been fun but it would be sure nice if your comments accepted some formatting!
7/9/2015 10:51 PM | Rob
Gravatar

# re: Little Puzzlers–The Majority Element

Have empty hash table and linked list
Traverse array to be checked
At each value, check if it's in the hash table.
- If so, increment hash table value by 1
- If not, add value to linked list, then add to hash table
After traversing array is finished, run through the linked list and keep track of the highest value at each hashed element. If > n/2, you've found your max
7/10/2015 10:35 AM | JP
Gravatar

# re: Little Puzzlers–The Majority Element

James: Size of the list is not guaranteed to be known.

Rob: Yes, that is the optimal solution. 2 O(n) passes and constant memory footprint. And yes, the formatting of comments is not optimal on this blog.

JP: That also works, it's worst-case 2 O(n), but uses O(n) memory potentially. Performance wise excellent.



7/10/2015 2:37 PM | James Michael Hare
Gravatar

# re: Little Puzzlers–The Majority Element

James: Ah yes, I did not read Rob's solution before posting mine. His is a very clean, and a clever solution. I was aware of my O(n) memory usage but I could not conceive how to achieve O(1) memory usage. (aside: he is very correct about the formatting for code comments.)

Rob: You used a clever little trick I've seen in a tic-tac-toe end-game logic somewhere, in incrementing what you are counting, and decrementing when you see otherwise. Well done.
7/10/2015 3:24 PM | JP
Gravatar

# re: Little Puzzlers–The Majority Element

>> 'Size of the list is not guaranteed to be known."

Which puts another wrinkle in this, as it implies the data is coming in as a stream, which mean we cannot guarantee it can be iterated over twice, which is needed for Rob's and JP's solutions.
7/13/2015 1:39 PM | James Curran
Gravatar

# re: Little Puzzlers–The Majority Element

@James: No, let me clarify. I just mean the size of the list isn't necessarily known as part of what you're given. It may be a bounded IEnumerable<T> but you aren't given a Count as part of the interface.

You may assume you can re-iterate over the sequence, though we'd still prefer a O(1) storage solution to O(n)
7/14/2015 3:58 PM | James Michael Hare
Gravatar

# re: Little Puzzlers–The Majority Element

Best and best blackrabbitcoder
12/1/2016 3:48 AM | Mark
Post A Comment
Title:
Name:
Email:
Comment:
Verification:
 

Powered by:

Copyright © James Michael Hare