Question

There are n marble balls, one of which is made of a different material. You have access to a Comparator that can compare two inputs (of an arbitrary number of marble balls) and determine if the two inputs are the same or not. The problem is to find the single marble ball that is different from the others while minimizing the number of times you access the Comparator. Design an efficient algorithm based on prune-and-search to solve the problem. Derive the time complexity of your algorithm

Answer 1

Algorithm:

1. Divide n in three equal groups if n is divisible by 3.

1.1 If n gives remainder 1 on dividing by 3, compare this extra marble with any other marble and if they are same, remove this extra marble, if not take any other marble and compare this extra marble with this. If both are same, the marble that we used for previous comparison is the answer else the extra marble is the answer.

1.2 If n gives remainder 2 on dividing by 3, check if this two extra marbles are same by comparator. If they are same remove them else chose any one marble from the group and compare any of the extra marble. If they are same the other extra marble is the answer else the chosen extra marble to compare is the answer..

2. Take group 1 marbles and group 2 marbles and compare using a comparator. If both groups are same, consider third group. If both groups are not same, compare first and third group. If both are same then consider group 2 else consider group 1.

3. Recursively follow steps 1 and 2 till different marble is found.

Here, a group (or extra marble(s)) are prune and search is done on rest.

Time complexity can be given by:

T(n) = T(n/3) + 1

This is because in the worst case, we perform the recursive action on 1/3 of the marbles everytime and comparator takes a constant time.

Applying master theorem to get time complexity. a = 1, b = 3 and f(n) = 1

It satisfies If f(n) = Θ(n ^{log_b a} ), then T(n) = Θ(n ^{log_b a} log n) . So,

T(n) = Θ (n ^log₃(1) log n) = Θ (log n)

Hence, time complexity of this algorithm is Θ(log n)