A Problem Like This Can Baffle You In Your Next Interview

image containing math problem statement
An easy and beautiful problem, which will help you think in an iterative manner.
Problem contributed by debosmita1729
-----------book page break-----------
Given any number of balls, $n$, we can divide the balls into three groups, such that two of them are equal and a third one may or may not be equal to the first two (depending on whether $b$ is divisible by $3$ or not).
If $b \% 3  = 1$, then the third group will have $\left\lfloor \dfrac{n}{3} \right\rfloor + 1$, or if $b \% 3 = 2$ then the third group will have $\left\lfloor \dfrac{n}{3} \right\rfloor + 2$ balls, while each of the first two groups will have $\left\lfloor \dfrac{n}{3} \right\rfloor$ balls.
We can compare the first two groups, and if both groups weigh equal then the third group contains the defective ball, or else the lighter group contains the defective ball.
Finally, for the boundary condition, if we have $2$ or $3$ balls we can identify the defective ball with just one measurement.

If the given number, $n$ is a power of $3$, let's say $3^a$ then we can keep dividing till we are left with exactly $1$ ball. This can be done in $log_3 (3^a) = a$ steps.
But if the number of balls is not a power of $3$, then the worst case scenario will occur, when after every division, the largest group will contain $3k + 2$ where $k$ is any integer.

This condition will arise when the total number of balls, $n = 3^a + 2$ balls.
This will lead to the formation of the following groups:
$3^{a-1}$, $3^{a-1}$ and $3^{a-1} + 2$ after the first step
$3^{a-2}$, $3^{a-2}$ and $3^{a-2} + 2$ after the second step
$...$
$1, 1, 3$ after $a$ steps.

-----------book page break-----------
At this stage, if the defective ball is in the group of $3$ we need one additional measurement to find the defective ball.

Therefore, to find the defective ball from a given set of $n$ balls, we need a total of $\left\lceil \log_3 {n}\right\rceil$ measurements, where $\left\lceil \ \right\rceil$ is the smallest integer (ceiling) function.

Therefore, for the given value of $256$ the number of measurements will be $\left\lceil \log_3 {256}\right\rceil = \left\lceil 5.xxx \right\rceil = 6$.
If we look at the worst case scenario at each step, here is how the measurements will look like:
$256 = 85 + 85 + 86$

$\text{(After step 1): }86 = 28 + 28 + 30$

$\text{(After step 2): }30 = 10 + 10 + 10$

$\text{(After step 3): }10 = 3 + 3 + 4$

$\text{(After step 4): }4 = 1 + 1 + 2$

$\text{(After step 5): }2 = 1 + 1$

$\text{(After step 6): }1 = 1$