Double Cola

Key observation

The queue looks chaotic if you stare at individual people. That’s bait. Don’t simulate the queue — it grows forever and $n$ can be as large as $10^9$.

Instead, group the process into rounds.

Initially, the order is:

$$\text{Sheldon},\ \text{Leonard},\ \text{Penny},\ \text{Rajesh},\ \text{Howard}$$

In the first round, each person drinks once:

$$1,1,1,1,1$$

After that, each person has been duplicated, so in the next round each name appears twice consecutively:

$$2,2,2,2,2$$

Then four times each:

$$4,4,4,4,4$$

And so on. In round $k$, every name appears $2^k$ consecutive times, so the whole round contains:

$$5 \cdot 2^k$$

cans.

Reducing $n$

Let $len$ be the number of consecutive copies of each name in the current round.

Start with:

$$len = 1$$

The current round has:

$$5 \cdot len$$

positions. If $n$ is larger than that, the answer is not in this round, so subtract the whole round:

$$n \leftarrow n - 5 \cdot len$$

Then move to the next round:

$$len \leftarrow 2 \cdot len$$

Repeat until:

$$n \le 5 \cdot len$$

Now $n$ is the position inside the current round.

Finding the name

Inside a round with block size $len$, the layout is:

$$\underbrace{S\ldots S}_{len}, \underbrace{L\ldots L}_{len}, \underbrace{P\ldots P}_{len}, \underbrace{R\ldots R}_{len}, \underbrace{H\ldots H}_{len}$$

So the zero-based index of the answer is:

$$\left\lfloor \frac{n-1}{len} \right\rfloor$$

The $n-1$ matters because cans are numbered from $1$, but arrays are indexed from $0$. Classic off-by-one trap. It wants your blood.

Example

For $n = 6$:

• Round with $len = 1$ has $5$ cans.
• Since $6 > 5$, subtract it:

$$n = 6 - 5 = 1$$

• Now $len = 2$.
• Position $1$ in this round belongs to:

$$\left\lfloor \frac{1-1}{2} \right\rfloor = 0$$

So the answer is Sheldon.

Complexity

Each iteration doubles $len$, so there are only about $\log_2 n$ iterations.

$$O(\log n)$$

time and

$$O(1)$$

extra memory.