Luigi has N balls. The balls look identical. However, there is one ball that is heavier. The rest share the same weight. Luigi is so cool he has a balance to weigh the balls.
At each weighing he can choose two disjoint subsets of balls and compare them.
Luigi wants to compute the minimum number of weighings after which he is 100% sure which ball is the special one.
Input
The first line of the input contains an integer N denoting the number of balls.
Output
The only line of output should contain an integer denoting the minimum number of weighings after which he is 100% sure which ball is the heavier one.
Restrictions
- 1 ≤ N ≤ 1018
- Two sets are disjoint if and only if they have no element in common.
Sample
| Input | Output | Explanation |
|---|---|---|
| 2 | 1 | We can compare the two balls and see which one is heavier. |
| 4 | 2 | We can make 2 groups of 2 balls each and decide which is heavier. Then, we can split that group in 2 groups of 1 ball, compare them and decide which is the heavier among all. |
| 9 | 2 |
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))
