Finding Majority Element

Jargon: Majority Element is an element of an array that occurs more than half the number of times in the array. Also, [x] means smallest integer greater than x.

Problem 1: Assume that an integer array A[1..n] has a majority element and elements other than majority element are distinct. How to find majority element. What's the space and time complexity of the algorithm ?

Complexity: Time Complexity = n/2(comparisons), Space Complexity = O(1)

Solution: show

We will use pigeonhole principle to make our clever observations. There can be a maximum of [n/2]-1 elements that are distinct, remaining [n/2] element have to be same (as majority element exists in the array). We can consider that the [n/2]-1 distinct elements to be laid out and the space between two laid out elements to be a basket of infinite size. So we will have [n/2] baskets. If we try to distribute [n/2] majority element to these baskets, then in only one permutation will each basket get one element. Otherwise, some baskets would get more than one element and some baskets would remain empty.

Using this observation, we can claim that to find majority element we need to check adjacent elements for equality or two hop neighbor (adjacent to neighbor) for equality. That requires two comparison per element and the algorithm would look like this:

for i <- 1 to n-2
  if A[i] == A[i+1] or A[i] == A[i+2]
    return A[i]

A quick observation tells that this algorithm's for loop would stop when i=[3n/4]+1 even in worst case and the number of comparisons done will be ~ 3n/2. Now, we can make another clever observation that is, if we do not find two adjacent elements to be equal after complete scanning of array, then first element has to be majority element by pigeonhole principle.

for i <- 1 to n-1
  if A[i] == A[i+1]
    return A[i]
return A[1]

In Worst case this algorithms stops at i=n+1 and the number of comparisons done is = n-1. Even though this looks better than the first solution but it could be worse in practice. On a highly pipelined architecture with branch prediction, first one is much better than the second one, even though it does more comparisons per loop. So testing for large array sizes with random shuffling of elements will give clear insight into which algorithm is faster. Now an extremely clever solution which is based on observation that if we pair array elements and strike out a pair if its both the elements are distinct or else return the pair element as majority element. If all pair are striked out then what ever element is left has to be majority element.

i = 1
while i <= n 
  if A[i] == A[i+1]: return A[i]
  i+= 2

return A[n]

Worst case analysis tells that algorithms would stop when i=n-1 and the number of comparisons done is ~ n/2. This is indeed the best in worst case that we can do.

Problem 2: Assume that an integer array A[1..n] has a majority element and elements other than majority element need NOT be distinct. How to find majority element. What's the space and the time complexity of the algorithm?

Complexity: Time Complexity=n(comparison), Space Complexity=O(1)

Solution: show

This algorithm uses an observation that if we consider our array to be list of voters and array value is the candidate to whom they are voting, then majority element is the winning candidate. Additionally, if all other candidates are merged to form one candidate then still it will fail to defeat the majority element candidate (hence the name majority element). So we can think of it this way. Assuming a negative vote decrease the count of majority element then still the count of majority element would be atleast 1. This algorithm implements the above idea.

element = A[1]
votes = 1
for i <- 2 to n:
  if A[i] == element
    votes += 1
  else if votes > 0
    votes -= 1
  else:
    element = A[i]
    votes = 1

return element

This algorithm does n-1 comparisons. The comparisons such as votes > 0 don't count as they are integer variable comparison.

Problem 3: Now consider that there are k majority elements, i.e., each of the k majority elements appear in the array more than ceil(n/(k+1)) times. How do we find the k majority elements. (Problem 2 is a special case of this problem with k=1).  

Complexity: Time Complexity=k*n(comparison), Space Complexity=O(k)  

Solution: show

Algorithm uses the same intuition as that presented for problem 2. But instead of one counter, we keep k counters. Each counter is initialized with a unique element from the array and we maintain count of how many times that element has been seen so far. Now for a new element x, if it matches an element in the counter then its count is incremented by 1. If the counter of an element is 0 then the x replaces that element and its count is set to 1. If x doesnt match any element on the counter, and all elements have count > 0, then all counters are decremented by 1. Then we move to next element. Following code implements this logic.

for i = 1:n
   // update element count in majority array
   for j = 1:k
      if Maj[j] == A[i] 
         Count[j] += 1
         break
      end
   end
   
   // succeeded in above operation (dont go below)
   if k > j
      continue
   end
   
   // Came here, it means that element not in 
   // majority array (put it in an empty slot)
   for j = 1:k
      if Count[j] == 0
         Maj[j] = A[i] 
         Count[j] = 1
         break
      end
   end
   
   // succeeded in above operation (dont go below)
   if k > j
      continue
   end
   
   // Came here, it means that no empty slow 
   // (decrement counts of all majority elements)
   for j = 1:k
      Count[j] -= 1
   end
end   

The algorithm runs in O(nk) time and takes O(k) extra space. It is easy to see that algorithm finds all the k majority elements. This is becase a non-majority element can knock of all the K majority element once. Since there are less than n - k*ceil(n/(k+1)) (< n/(k+1)) non-majority elements, majority elements will survive in the Maj array.

Airplane Seating Problem

100 passengers are boarding an airplane with 100 seats. Everyone has a ticket with his seat number. These 100 passengers boards the airplane in order. However, the first passenger lost his ticket so he just take a random seat. For any subsequent passenger, he either sits on his own seat or, if the seat is taken, he takes a random empty seat. What's the probability that the last passenger would sit on his own seat?

Answer: 1/2

Solution:
When 100th passenger arrives, only seat 1 or 100 is vacant (rest all must be non-empty). To see this, let seat 50 is vacant. Since passenger 50 came before passenger 100, he would sit in his seat only. Hence seat 50 cannot be vacant. So all permutations of the seating arrangement would result in last person sitting in either seat 1 or seat 100. Both the options are equi-likely.

Tip: Its wiser to solve problems like these for small values and then try to generalize. For e.g. let there be three passengers p1, p2, p3. p1 can sit in seat 1 with prob=1/3. In this case p3 sites in seat 3. p1 can sit in seat 2 with probability = 1/3, p2 can sit in either seat 1 or 3 (with prob=1/2). so p3 gets to sit in his seat with probability = 1/3 * 1/2 = 1/6. p1 can sit in seat 3 with probability 1/3. In this case p3 can sit in seat 3 with probability = 0. So the total probability for p3 to sit in his seat = 1/3 + 1/6 + 0 = 1/2

Tic Tac Toe

Two players are playing a game and take alternating turns. There are 9 cards on the table with numbers from 1 to 9. On each turn, a player picks one card from the table. The first player to have 3 cards that total a sum of 15 wins. If no one can after all cards are distributed, then it's a draw. Can you tell who wins, assume both players are highly and equally intelligent and what is the winning strategy ?
Source: Petr Mitrichev's Blog

Answer: Draw

Solution:
If player 1 picks any card except for 5 then there are three ways he can pick second card in order to total 15. Player 2 will block one way in his following turn. Leaving two options for player 1. For any way that player 1 chooses, he has just one way now to total 15. Player 2 will block that way. Player 2 has blocked all ways of player 1 so far. But in the two moves so far player 2 has one way to reach 15. Player 1's next turn can block that. But, This analysis is hard to follow and unclear to see for all the possible combination.

This problem can be modeled in form of tic-tac-toe by constructing a 3 x 3 magic square, as follows:

4  9  2
3  5  7
8  1  6

Now all rows, diagonals, columns sum to 15. So the problem is reducible to playing a tic-tac-toe. Its easy to see that if two players are highly and equally intelligent then the game would result in a draw.

Math Magician

A magician has one hundred cards numbered 1 to 100. He puts them into three boxes, a red one, a white one and a blue one, such that each box contains atleast one card. A member of audience draws two cards from two different boxes and announces the sum of the number on those cards. Given this information magician locates the box from which no card has been drawn. How many ways are there to put the cards in the boxes so that the trick works.
Source: International Maths Olympiad 2000

Answer: 12

Solution:
We split the possible arrangements into two different cases.

Case 1: Assume that there exists an i such that i, i+1, i+2 go in different box (say wrb). Since, (i+1) + (i+2) = i + (i+3) => (i+3) should go in white box. Similarly i-1 should go in blue box. Since the pattern repeats without much choice so it boils down to assigning different boxes to first three cards. Total of 6 ways.

Case 2: Assume that no three neighbors are put in different boxes. Let card 1 be in white box. Let i be the smallest card to go in red box (such that i > 2). Let j be the smallest card to go in blue box (such that j < 100). Let j > i.

==> i-1 is in white box.
==> i + j = (i-1) + (j+1)
==> j+1 is in white box.

==> i + (j+1) = (i+1) + j
==> i+1 is in blue box
==> j = i+1

This violates the main assumption from both ends i-1, i, i+1 are in different boxes and also i, i+1, i+2, hence j = 100. so that j+1 doesn't exist and both 99 and 98 belong to same box other than blue.

also (i-1) + 100 = i + 99 => card 99 is in red box => card 98 is in red box

but 2 + 99 = 1 + 100 => 2 is red. in general assume that there exists a card c (>1) and it belongs to white box and also c-1 to white box. => c + 99 = (c-1) + 100. which leads to failure of the trick. Assuming cards surrounding c are red. c + 99 = c-1 + 100 => failure of trick. Hence no such c exists and c=1 is the only card in white box.

hence the combination looks like wrrrr.........rrrrrb i.e. one card (value 1) in white box, one card (value 100) in blue box and rest all cards in red box. There are six ways of such arrangements.

Unbiased Coin Tossing

Given a biased coin, with probability of Heads equal to x. How to do unbiased coin tossing?

show

Lets define an event, E as tossing the biased coin twice. The possible outcomes with probabilities is as follows

P(h,h) = x^2
P(h,t) = x(1-x)
P(t,h) = x(1-x)
P(t,t) = (1-x)^2

The event h,t or t,h are equi-likely, without any bias we can call that if Event h,t occurs it means head, t,h means tails but if h,h or t,t occurs we repeat the experiment.

Try to find the expected number of coin toss that would be required to call heads or tails?

show

Let expected coin toss be e.

Probability that we get outcome in 1st event is 2x(1-x)
Total number of coin toss would be 2
Probability that we get no outcome in 1st event is [1 - 2x(1-x)]
Total number of coin toss would be 2 + e (we wasted 2 coin toss and still we expect e)

==> e = 2 * 2x(1-x) + (2+e) * [1 - 2x(1-x)]
==> e = 4x(1-x) + 2 - 4x(1-x) + e - 2ex(1-x)
==> e = 1/ [x(1-x)]

so for x = 1/2, e = 4
for x=2/3, e = 4.5
for x=1, e = INF (as expected, because all we get is chain of h h h h h)

What is the probability that there wont be any outcome in e coin tosses (expected outcomes)?

show

p = prob of e heads + prob of e tail
==> p = x^e + (1-x)^e

To find a bound on this p in polynomial terms can be done by using binomial expansion and Newtonian series is out of the scope of this blog. But some number crunching is.

For x = 1/2, e = 4, p = 0.125
For x = 2/3, e = 4.5, p = 0.168
For x = 3/4, e = 5.33, p = 0.216
For x = 0.99, e = 101, p = 0.362

This tells us that probability that outcome comes is quite good even for high coin biases.

How can we improve on the expected number of coin tosses?

show

In above method, we say that HT or TH terminates experiment. and continue the experiment a fresh when the outcome is HH or TT.

We can further combine outcome of two such events to increase the probability of outcome e.g. say HH TT => heads and TT HH means tails.

How much expected coin tosses are we doing in this case?

show

try