Category Archives: Riddles

Split the Bill

Posted on by
Reply

Ok, here is the problem. You are at a restaurant with a number of your friends, and the bill comes. But you have a 5, and two 10s. But your bill is 17. And your friend has 2 ones, and a 20. And another friend has three 10s. You need to split the bill–you want everyone to pay for their share, but find a way to redistribute the money without getting change. It’s a tricky problem–what if he gives two dollars to her, and then she gives a five to him…etc.

Can you write a program that splits the bill?

More specifically, can you write a program that given a list of people, where a person has an amount that they owe and a list of bills that they have, outputs whether or not it is possible to split the bill? Can you write one that shows exactly where the money needs to go?

To start off:

you have a vector called people
a person has a name, list of bills, and total amount owed
write:

bool SplitTheBill(people);

Riddle: List of Numbers, Each Appears Twice …

Posted on by
1

So here is the riddle:

There is a list of numbers, where each number appears in the list twice. Except there is one number that appears once. I give you the list one number at a time.

The question is: can you find out what the number is that appears only once?

You can’t save the whole list and then look at it later. You can only store at most one number. In jargon, you must do it in constant space.

For example if I gave you the list 1,3,5,3,8,5,1, then 8 is the number that only appears once.

UPDATE:
So the condensed version of riddle is:
Given a list of numbers read off one by one where each number appears twice, and one number that appears once, can you find the number that appears once by only storing one intermediate number?