Brian's Programming Challenges

Majority Algorithm.
Imagine that there's a huge election being held to determine who is the coolest dØØd in the world. Naturally everyone's a candidate (altough some people have a better chance at winning than others.) A person must receive over half of the total votes in order to become the worlds coolest dØØd. Everyone on Earth is given a unique positive number to identify them. To vote for a particular person, you simply have to put his or her number in the ballot box.

When the election is over, we're left with the task of figuring out if anyone got a majority of the votes. Since there are so many votes to count, it's been decided that the tallying of votes needs to be computerized. All the votes have been stored in a large ROM chip. Unfortunately, the voting office only has a Timex Sinclair with 1K of RAM with which to perform its calculations. Therefore, it would be helpful if you could write a program which didn't use too much space and could determine who the majority winner is (or if one doesn't exist) without having to look at each vote in the ROM too many times (since there are so many votes.)

Formally: Given an array, A, consisting of N (N>0) positive integers, write a function which finds the integer that occurs a majority of the time in the array [if it exists] and return it. If it doesn't exits, return 0. The function must run in O(1) space and O(N) time.

Solution (pdf/postscript/html)

Fraction Counting Algorithm.
We're all familiar with counting in positive integers. For instance, if I were to ask you to come up with an algorithm for printing out the integers from 1 to N, you would probably have no problem writing this algorithm. In fact, you would probably have no problem making the algorithm run in in O(1) space and O(N) time!

Now let's look at a similar problem in fractions. Given an integer N, write an algorithm which outputs all of the fractions between 0 and 1 whose denominators do not exceed N. For instance, if N were 5, your algorithm would output 1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5. Your challenge is to write this fraction counting algorithm in O(1) space and O(number of fractions) time.

Solution (pdf/postscript/html)

Coconut Divisibility Problem.
Four boys go camping one weekend. While in the wilderness, the boys collect a number of coconuts. They take the coconuts back to their cabin and agree to divide them up equally before they leave the next morning. That night, one of the boys wakes up (from excitement) and decides to gather his share of coconuts right that moment. However, when he counts the coconuts he finds that the number is not divisible by 4, but by giving one coconut to the pet monkey, the remaining amount is divisible by 4, so the boy gives one coconut to the monkey and takes 1/4 of the rest for himself.

Later that night another boy wakes up (also from excitement) and decides to gather his share of coconuts right that moment (not realizing that the other boy has already taken his share.) When he counts the number of coconuts he finds that if he gives one to the pet monkey then the remaining amount will be divisible by 4, so the boy gives one coconut to the monkey (who has already disposed of the previous one) and takes 1/4 of the rest for himself.

The remaining two boys also wake up one by one in the middle of the night in order to get their share of coconuts, and they both have to give one coconut to the monkey before taking 1/4 of the rest.

In the morning, as the boys are leaving the cabin, they notice that there are still some coconuts left. Since each of them has taken their share, they're not really sure why there should be any left. Not wanting to think about it too hard, though, they just decide to split the remaining coconuts evenly since the remaining amount is exactly divisible by 4.

Question: How many coconuts were there to begin with? Give the minimum possible value.

Harder Question: What would the solution be if there were N boys instead of 4 (i.e. replace '4' in the problem with 'N')

Solution (pdf/postscript/html)