Majority element of an array

Given an array of n number, find the majority element (if any)?

(Majority element is the one which occurs more than n/2 number of times)

Example: A = [20, 4, 4, 7, 4, 16, 20, 4, 0, 4, 4], n = 11, '4' occurs 6 times, is the majority elemet.

How to go about it? Simplest method follows. Keep another array of counts and keep track of which number occurs how many times. But, this is possible only when we know the range of numbers. Even though we know that, it is inefficient in space. So, let's rule out that method. What we have to thus look for, is a way to keep counts / track of a possible majority element run time. How to do this?

What if we consider the smaller part of above given A? We start with count=0. At index_0, we assume 20 is the majority element, thus setting count to 1 and also keep track that '20' is our probable majority number so far. At index_1, we find that the number is not 20 and thus we have lost on score, thus decrementing the count, so not it is 0 again. Here, we are kind of sure that from the elements we have seen so far, each appeared with equal counts and thus, we should look for a new start. So, when count hits 0, we change our probable majority element to the current one and again repeat the process.

With above example, count and probable majority element (pme) go as follows.
A        = [20, 4, 4, 7, 4, 16, 20, 4, 0, 4, 4]
count = [  1, 0, 1, 0,  0,  0,   0, 0, 0, 0, 1]
pme   = [20, 4, 4, 7, 4, 16, 20, 4, 0, 4, 4]

Thus, in O(n) we can find the majority element.

Prime number pairs summing to an odd number

While reading a book (details below), I came across a very nice problem as follows.

Find all pairs of prime numbers that sum up to 999.

As the book says, it involves thinking before actually attacking the problem. Few observations:

• Sum given is odd (999).
• To get sum odd, exactly one of the two numbers have to be even.
• Asked are the pairs of prime numbers.
• Meaning, we want intersection of prime and even which is just the number 2.

So, one of the numbers has to be 2; and thus the other of course is 997. And, that's the only pair of prime numbers which sums up to  999.

Cool indeed! :)

Book details:
Title:  math Charmers - Tantalizing Tidbits for the mind
Author: alfred s. posamentier
Publisher: University Press