Let's examine the case with 9 balls.
First of all, we can group the 9 balls in the 3 groups, each having 3 balls. Let's call them group1, group2 and group3.
We will weight 2 of them and it will result some cases:
- (group1 == group2) - if the 2 groups we weight are equal then the heavier ball will be in the 3rd group which we have not weighted yet (group3)
- (group1 != group2) - if one of them is heavier then we have found the group which is heavier so either group1 or group2
Now we only have 3 balls left to weight (in each of the 2 cases described above). We apply the same idea again. So, we will weight only 2 balls and see if they are equal then the heavier is the 3rd one. Else one of the 2 balls is the one.
So we have managed to find the heavier ball by making only 2 weighings. Now we can apply the same idea (of splitting the input into 3 groups) to any input. So, the answer will be log3(n-1) which can be calculated in O(1) or in O(log3(n))
