Loading…

mediumBit ManipulationSometimes asked

Counter Game

Q: How do you solve Counter Game using the Simulation — Play Out Every Move approach?

When to use it: Say this first: it mirrors the rules exactly and confirms the parity argument with no leap of faith. Replay the game move by move, counting turns. **The loop.** While `N > 1`: if `N` is a power of 2 (`N & (N − 1) == 0`), set `N = N / 2`; otherwise subtract the largest power of 2 below `N` (the value of its highest set bit). Increment a move counter each time. **Why this terminates fast.** Halving a power of two reduces its bit index by one. Subtracting the top bit of a non-power-of-two clears that bit. Either way the highest set bit strictly decreases over time, so we reach `N == 1` within O(log N) moves. **Reading off the winner.** Louise moves on turns 1, 3, 5, … and Richard on 2, 4, 6, …. The player who performs the move that lands on 1 wins, so if the total move count is odd Louise made it (Louise wins), and if even Richard did. The `N == 1` start means the loop body never runs (0 moves) → Richard. **Why we still look for the formula.** Simulation is already efficient, but recognizing that the moves are pure bit operations lets you state the answer in closed form and explain the structure — which is what the interviewer is really probing. Time complexity: O(log N). Space complexity: O(1).

Q: How do you solve Counter Game using the Bit Formula — Popcount and Trailing Zeros (Optimal) approach?

When to use it: The insight they want. Say 'moves = (popcount − 1) + trailing-zeros, then check parity'. Count the moves directly from N's binary representation. **Subtracts clear high bits.** While N has more than one set bit it's never a power of 2, so every move is a subtract, and each subtract clears the current highest set bit. Starting from `popcount(N)` set bits, it takes `popcount(N) − 1` subtracts to reduce to a single remaining bit. Because subtracts remove bits from the top, the bit that survives is the LOWEST set bit of the original N. **Halvings shift the survivor down.** Once only one bit remains, N is a power of 2 at position `t = lowestSetBitIndex(N)`. Each halving lowers that bit's position by one, so it takes exactly `t` halvings to reach position 0 (value 1). **Total and parity.** `moves = (popcount(N) − 1) + trailingZeros(N)`. Louise moves first, so she wins iff `moves` is odd; otherwise Richard. The special case `N == 1` gives `popcount = 1`, `trailingZeros = 0` → `moves = 0` (even) → Richard, matching the rule that an initial 1 is a Richard win. **Why it matches the simulation.** It's the same sequence of moves, just counted by structure instead of replayed — O(1) versus O(log N). Time complexity: O(1). Space complexity: O(1).

Bit Manipulation · 17 of 20 · 8 min

Louise and Richard play a game starting from a counter N. They take turns, Louise first. On each turn the current player does one of two things:

If N is a power of 2, divide it by 2.
Otherwise, subtract the largest power of 2 that is less than N.

The player who first makes the counter reach 1 wins. If N is initially 1, Richard wins (Louise never gets to move). Return the name of the winner.

In plain English

Neither player has a meaningful choice — the move is fully determined by whether N is a power of 2. So the entire game is decided before it starts: count how many moves it takes to reach 1, and the parity tells you who made the final move. Louise makes moves 1, 3, 5, …; Richard makes moves 2, 4, 6, …. The two operations are exactly bit operations: subtract-largest-power clears the top set bit, halve shifts the lone bit down.

Examples

Example 1

Input: N = 6
Output: Richard
Note: 6 (110) is not a power of 2 → subtract 4 → 2 (move 1, Louise). 2 is a power of 2 → halve → 1 (move 2, Richard). 2 moves total (even) → Richard wins.

Example 2

Input: N = 132
Output: Louise
Note: 132 = 10000100. Subtract 128 → 4 (move 1). 4 → 2 (move 2). 2 → 1 (move 3). 3 moves (odd) → Louise wins. Formula: popcount(132)=2, lowest set bit at index 2 → (2−1)+2 = 3.

Example 3

Input: N = 1
Output: Richard
Note: Counter already at 1; 0 moves → Richard wins.

Constraints

1 ≤ N < 2⁶⁴ (can exceed 32-bit range — use a 64-bit/unsigned-safe type)
1 ≤ number of games (test cases) ≤ 100
Louise always moves first
If N == 1 at the start, the winner is Richard

Clarifying questions4First question: Do players ever have a choice that affects the outcome?Explore questions

Q1.Do players ever have a choice that affects the outcome?
No. The rule is forced by whether N is a power of 2. So the game is deterministic and the winner depends only on the move count's parity.
Q2.What happens if N starts at 1?
The counter is already 1, so no move is made (0 moves). Louise never moves; Richard wins by the problem's definition.
Q3.How big can N get?
Up to just under 2⁶⁴, which overflows a signed 32-bit int. Use a 64-bit type (and treat it as unsigned where needed); Python integers handle it natively.
Q4.Why does subtracting the largest power of 2 below N clear the top bit?
When N is not a power of 2, its highest set bit has value < N, and that value IS the largest power of 2 below N. Subtracting it zeroes that bit and leaves the rest untouched.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Louise and Richard alternate, Louise first. On a turn: if N is a power of 2, halve it; otherwise subtract the largest power of 2 less than N. Whoever makes N reach 1 wins. The winner is decided purely by the parity of the number of moves. Simulating the moves is O(log N) per turn. The bit insight: subtracting the largest power of 2 below N just clears N's highest set bit, and halving a power of 2 shifts its single bit down. So the total moves = (popcount(N) − 1) + (index of N's lowest set bit). Louise wins on odd move count, Richard on even (and Richard wins immediately when N starts at 1).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize the moves are forced (no real choice), so the winner is just the parity of the move count, and whether you can map the two operations to bit clears and shifts to count moves without simulating.

Where candidates slip

Getting the parity backwards (Louise vs Richard), forgetting that N == 1 is an immediate Richard win, or overflowing on N up to 2^64 by using a signed 32-bit type.

How to stand out

State that the game is deterministic so only move parity matters, simulate to confirm, then give the O(1) bit formula: moves = (popcount(N) − 1) + trailingZeros(N), Louise wins iff that's odd.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Simulation — Play Out Every Move	`O(log N)`	`O(1)`	Say this first: it mirrors the rules exactly and confirms the parity argument with no leap of faith.	Read
2	Bit Formula — Popcount and Trailing Zeros (Optimal)Optimal	`O(1)`	`O(1)`	The insight they want. Say 'moves = (popcount − 1) + trailing-zeros, then check parity'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCounter Game: who wins?Any real choice?No, forcedExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Simulation — Play Out Every Move

TimeO(log N)SpaceO(1)

Say this first: it mirrors the rules exactly and confirms the parity argument with no leap of faith.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The move is forced: if N is a power of 2, halve it; otherwise subtract the largest power of 2 below N.

2Hint 2Explore hint

Detect a power of 2 with N & (N − 1) == 0. The largest power of 2 ≤ N is the value of its highest set bit.

3Hint 3Explore hint

Count moves until N becomes 1. Louise made the odd-numbered moves, so odd count → Louise, even → Richard.

A · Core idea

Replay the game move by move, counting turns.

The loop. While N > 1: if N is a power of 2 (N & (N − 1) == 0), set N = N / 2; otherwise subtract the largest power of 2 below N (the value of its highest set bit). Increment a move counter each time.

Why this terminates fast. Halving a power of two reduces its bit index by one. Subtracting the top bit of a non-power-of-two clears that bit. Either way the highest set bit strictly decreases over time, so we reach N == 1 within O(log N) moves.

Reading off the winner. Louise moves on turns 1, 3, 5, … and Richard on 2, 4, 6, …. The player who performs the move that lands on 1 wins, so if the total move count is odd Louise made it (Louise wins), and if even Richard did. The N == 1 start means the loop body never runs (0 moves) → Richard.

Why we still look for the formula. Simulation is already efficient, but recognizing that the moves are pure bit operations lets you state the answer in closed form and explain the structure — which is what the interviewer is really probing.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 6

Interactive diagram

Forced moves for N = 6

N=6

Active call / nodeSupporting contextReturned stateNot active

Each step is forced; we only count them.

Final resultRichard

C · Code with teaching comments

Reference implementation previewpublic String counterGame(long n) { int moves = 0; while (n > 1) { if ((n & (n - 1)) == 0) { // power of 2 → single set bit n >>= 1; // halveExplore the full code

solution.javaJava

Simulation — Play Out Every Move — reference

3 teaching notes

1
public String counterGame(long n) {
2
    int moves = 0;
3
    while (n > 1) {
4
        if ((n & (n - 1)) == 0) {        // power of 2 → single set bit
5
            n >>= 1;                     // halve
6
        } else {
7
            n -= Long.highestOneBit(n);  // subtract largest power of 2 below n
8
        }
9
        moves++;
10
    }
11
    // Louise made the odd moves, so odd total means she made the winning one.
12
    return (moves % 2 == 1) ? "Louise" : "Richard";
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(log N) timeO(1) spaceOpen the invariant and proofExplore the proof

Because every move is forced, simulation isn't a search — it's just counting. The whole problem is 'how many forced moves until 1, and is that odd or even?'.

ComplexityO(log N) time, O(1) space — Each move either halves N or clears its top bit, so N loses at least one bit position every move — at most O(log N) moves, each O(1).

E · Edge cases and pitfalls3Subtracting a power of 2 that's ≥ N — it must be strictly the largest power below N (the top bit, which is < N for non-powers).Explore edge cases

Pitfalls

Subtracting a power of 2 that's ≥ N — it must be strictly the largest power below N (the top bit, which is < N for non-powers).
Treating N == 1 as a Louise win — it's 0 moves, so Richard wins.
Using a signed 32-bit int and overflowing when N approaches 2⁶⁴.

03.2

Approach 2 of 2 · Optimal

Bit Formula — Popcount and Trailing Zeros (Optimal)

TimeO(1)SpaceO(1)

The insight they want. Say 'moves = (popcount − 1) + trailing-zeros, then check parity'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Map each operation to bits: subtracting the largest power of 2 below N clears N's highest set bit; halving a power of 2 shifts its single bit down by one.

2Hint 2Explore hint

So subtracts run until only one set bit remains — that's popcount(N) − 1 subtracts — and the surviving bit is the lowest one.

3Hint 3Explore hint

Then halvings carry that lowest bit down to position 0 — that's lowestSetBitIndex(N) halvings. Total = (popcount − 1) + trailingZeros.

A · Core idea

Count the moves directly from N's binary representation.

Subtracts clear high bits. While N has more than one set bit it's never a power of 2, so every move is a subtract, and each subtract clears the current highest set bit. Starting from popcount(N) set bits, it takes popcount(N) − 1 subtracts to reduce to a single remaining bit. Because subtracts remove bits from the top, the bit that survives is the LOWEST set bit of the original N.

Halvings shift the survivor down. Once only one bit remains, N is a power of 2 at position t = lowestSetBitIndex(N). Each halving lowers that bit's position by one, so it takes exactly t halvings to reach position 0 (value 1).

Total and parity. moves = (popcount(N) − 1) + trailingZeros(N). Louise moves first, so she wins iff moves is odd; otherwise Richard. The special case N == 1 gives popcount = 1, trailingZeros = 0 → moves = 0 (even) → Richard, matching the rule that an initial 1 is a Richard win.

Why it matches the simulation. It's the same sequence of moves, just counted by structure instead of replayed — O(1) versus O(log N).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 132 = 10000100

Interactive diagram

Bits to move count

popcount

Active call / nodeSupporting contextReturned stateNot active

popcount − 1 subtracts plus trailing-zeros halvings.

Final resultLouise

C · Code with teaching comments

solution.javaJava

Bit Formula — Popcount and Trailing Zeros (Optimal) — optimal

3 teaching notes

1
public String counterGame(long n) {
2
    int moves;
3
    // An initial 1 means zero moves; without this guard the formula still gives 0, but
4
    // the guard makes the rule explicit.
5
    if (n == 1) {
6
        moves = 0;
7
    } else {
8
        // popcount−1 subtracts to leave one bit, plus trailing zeros halvings to bring
9
        // it to 1.
10
        moves = (Long.bitCount(n) - 1) + Long.numberOfTrailingZeros(n);
11
    }
12
    // Parity of the move count names the winner — Louise on odd.
13
    return (moves % 2 == 1) ? "Louise" : "Richard";
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

The two operations are 'clear the top bit' and 'shift the lone bit down'. So the move count is read straight off N's bits: how many bits to clear (popcount − 1) plus how far the last one must fall (trailing zeros). Game theory collapses to two bit counts.

ComplexityO(1) time, O(1) space — A population count and a trailing-zero count are single built-ins (or O(word size) at worst). No loop over moves — constant time.

E · Edge cases and pitfalls6N = 1 — moves = 0 (even) → Richard, the immediate-win rule.Explore edge cases

Edge cases handled

N = 1moves = 0 (even) → Richard, the immediate-win rule.
N = 2 (power of 2)popcount 1, trailing 1 → moves = 0 + 1 = 1 (odd) → Louise; 2 → 1 in one halving.
N = 6popcount 2, trailing 1 → (2−1)+1 = 2 (even) → Richard, matching the simulation.

Pitfalls

Reversing the parity mapping (Louise on even instead of odd).
Using a 32-bit popcount/trailing-zero call on a value near 2⁶⁴ — use the 64-bit (Long) versions.
Counting the highest set bit instead of the lowest for the halving count.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String counterGame(long n) { int moves; if (n == 1) { moves = 0; } else {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Parity mapped to the wrong player

Louise moves first (turns 1, 3, 5…). If the total move count is odd, she made the last (winning) move. Swapping this reports the wrong winner.

Explore the code comparison

Don't write this

return (moves % 2 == 0) ? "Louise" : "Richard";

Write this instead

return (moves % 2 == 1) ? "Louise" : "Richard";

32-bit overflow on large N

N can be just under 2⁶⁴. A signed 32-bit int wraps around and corrupts both the power-of-two test and the move count.

Explore the code comparison

Don't write this

int n = readValue();           // overflows for N >= 2^31
while (n > 1) { ... }

Write this instead

long n = readValue();          // 64-bit; use unsigned-safe ops
while (n > 1) { ... }

Subtracting a power that's not strictly below N

The rule subtracts the largest power of 2 LESS than N. For a non-power-of-two that's its highest set bit; using N itself or a power ≥ N breaks the reduction.

Explore the code comparison

Don't write this

n -= 1 << n.bit_length()        # this is >= n

Write this instead

n -= 1 << (n.bit_length() - 1)  # highest set bit, < n

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Move count by bit structure → winner by parity

Code pattern to memorize

if N == 1: moves = 0
else: moves = (popcount(N) - 1) + lowestSetBitIndex(N)
return "Louise" if moves % 2 == 1 else "Richard"
# simulation form:
# while N > 1: if isPowerOf2(N): N >>= 1 else N -= highestPowerOf2BelowN; moves++

Rules to remember

1Power of two ⇔ a single set bit ⇔ `N & (N − 1) == 0`. Halving such a number shifts that one bit down by one position.
2When N is NOT a power of two, the largest power of 2 below N equals N's highest set bit, so subtracting it just clears that top bit.
3Therefore each subtract removes one high bit (popcount drops by 1) and each later halving moves the surviving lowest bit toward bit 0.
4Total moves = (popcount(N) − 1) subtracts to leave one bit, plus lowestSetBitIndex(N) halvings to bring it to bit 0.
5Louise moves first, so odd total moves → Louise wins, even → Richard. N == 1 means 0 moves → Richard wins immediately.

Use this pattern when

Alternating two-player game where the winner depends on the move count's parity
Operations that map cleanly to clearing or shifting bits
You can replace a simulation with a popcount / trailing-zero formula
Any 'halve if power of two, else subtract largest power of two' reduction

Choose another pattern when

Players have real choices that change the outcome → Sprague–Grundy / game DP, not a fixed move count
Operation set doesn't reduce to bit clears/shifts → simulate or model differently
You need the full move sequence, not just the winner → keep the simulation
N tiny and clarity matters more than speed → the simulation is plenty

Interview takeaway

The game is deterministic, so only the move count matters — and that count is fixed by N's bits: (popcount − 1) subtracts plus (lowest-set-bit index) halvings. Parity of that sum names the winner. Simulate for clarity, or compute it in O(1) bit ops once you see the structure.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternDeterministic game → parity of a bit-derived move count. When neither player has a real choice, the winner depends only on how many forced moves occur. Here the moves are bit operations, so the count is (popcount − 1) + trailing-zeros, and parity decides the winner.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Cipher

Continue · Next problem

Maximizing XOR

mediumBit ManipulationSometimes asked

Counter Game

Bit Manipulation · 17 of 20 · 8 min

Louise and Richard play a game starting from a counter N. They take turns, Louise first. On each turn the current player does one of two things:

If N is a power of 2, divide it by 2.
Otherwise, subtract the largest power of 2 that is less than N.

The player who first makes the counter reach 1 wins. If N is initially 1, Richard wins (Louise never gets to move). Return the name of the winner.

In plain English

Examples

Example 1

Input: N = 6
Output: Richard
Note: 6 (110) is not a power of 2 → subtract 4 → 2 (move 1, Louise). 2 is a power of 2 → halve → 1 (move 2, Richard). 2 moves total (even) → Richard wins.

Example 2

Input: N = 132
Output: Louise
Note: 132 = 10000100. Subtract 128 → 4 (move 1). 4 → 2 (move 2). 2 → 1 (move 3). 3 moves (odd) → Louise wins. Formula: popcount(132)=2, lowest set bit at index 2 → (2−1)+2 = 3.

Example 3

Input: N = 1
Output: Richard
Note: Counter already at 1; 0 moves → Richard wins.

Constraints

1 ≤ N < 2⁶⁴ (can exceed 32-bit range — use a 64-bit/unsigned-safe type)
1 ≤ number of games (test cases) ≤ 100
Louise always moves first
If N == 1 at the start, the winner is Richard

Clarifying questions4First question: Do players ever have a choice that affects the outcome?Explore questions

Q1.Do players ever have a choice that affects the outcome?
No. The rule is forced by whether N is a power of 2. So the game is deterministic and the winner depends only on the move count's parity.
Q2.What happens if N starts at 1?
The counter is already 1, so no move is made (0 moves). Louise never moves; Richard wins by the problem's definition.
Q3.How big can N get?
Up to just under 2⁶⁴, which overflows a signed 32-bit int. Use a 64-bit type (and treat it as unsigned where needed); Python integers handle it natively.
Q4.Why does subtracting the largest power of 2 below N clear the top bit?
When N is not a power of 2, its highest set bit has value < N, and that value IS the largest power of 2 below N. Subtracting it zeroes that bit and leaves the rest untouched.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Where candidates slip

Getting the parity backwards (Louise vs Richard), forgetting that N == 1 is an immediate Richard win, or overflowing on N up to 2^64 by using a signed 32-bit type.

How to stand out

State that the game is deterministic so only move parity matters, simulate to confirm, then give the O(1) bit formula: moves = (popcount(N) − 1) + trailingZeros(N), Louise wins iff that's odd.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Simulation — Play Out Every Move	`O(log N)`	`O(1)`	Say this first: it mirrors the rules exactly and confirms the parity argument with no leap of faith.	Read
2	Bit Formula — Popcount and Trailing Zeros (Optimal)Optimal	`O(1)`	`O(1)`	The insight they want. Say 'moves = (popcount − 1) + trailing-zeros, then check parity'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Simulation — Play Out Every Move

TimeO(log N)SpaceO(1)

Say this first: it mirrors the rules exactly and confirms the parity argument with no leap of faith.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

The move is forced: if N is a power of 2, halve it; otherwise subtract the largest power of 2 below N.

2Hint 2Explore hint

Detect a power of 2 with N & (N − 1) == 0. The largest power of 2 ≤ N is the value of its highest set bit.

3Hint 3Explore hint

Count moves until N becomes 1. Louise made the odd-numbered moves, so odd count → Louise, even → Richard.

A · Core idea

Replay the game move by move, counting turns.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 6

Interactive diagram

Forced moves for N = 6

N=6

Active call / nodeSupporting contextReturned stateNot active

Each step is forced; we only count them.

Final resultRichard

C · Code with teaching comments

Reference implementation previewpublic String counterGame(long n) { int moves = 0; while (n > 1) { if ((n & (n - 1)) == 0) { // power of 2 → single set bit n >>= 1; // halveExplore the full code

solution.javaJava

Simulation — Play Out Every Move — reference

3 teaching notes

1
public String counterGame(long n) {
2
    int moves = 0;
3
    while (n > 1) {
4
        if ((n & (n - 1)) == 0) {        // power of 2 → single set bit
5
            n >>= 1;                     // halve
6
        } else {
7
            n -= Long.highestOneBit(n);  // subtract largest power of 2 below n
8
        }
9
        moves++;
10
    }
11
    // Louise made the odd moves, so odd total means she made the winning one.
12
    return (moves % 2 == 1) ? "Louise" : "Richard";
13
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.13 lines

D · Why it works and complexityO(log N) timeO(1) spaceOpen the invariant and proofExplore the proof

Because every move is forced, simulation isn't a search — it's just counting. The whole problem is 'how many forced moves until 1, and is that odd or even?'.

ComplexityO(log N) time, O(1) space — Each move either halves N or clears its top bit, so N loses at least one bit position every move — at most O(log N) moves, each O(1).

E · Edge cases and pitfalls3Subtracting a power of 2 that's ≥ N — it must be strictly the largest power below N (the top bit, which is < N for non-powers).Explore edge cases

Pitfalls

Subtracting a power of 2 that's ≥ N — it must be strictly the largest power below N (the top bit, which is < N for non-powers).
Treating N == 1 as a Louise win — it's 0 moves, so Richard wins.
Using a signed 32-bit int and overflowing when N approaches 2⁶⁴.

03.2

Approach 2 of 2 · Optimal

Bit Formula — Popcount and Trailing Zeros (Optimal)

TimeO(1)SpaceO(1)

The insight they want. Say 'moves = (popcount − 1) + trailing-zeros, then check parity'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Map each operation to bits: subtracting the largest power of 2 below N clears N's highest set bit; halving a power of 2 shifts its single bit down by one.

2Hint 2Explore hint

So subtracts run until only one set bit remains — that's popcount(N) − 1 subtracts — and the surviving bit is the lowest one.

3Hint 3Explore hint

Then halvings carry that lowest bit down to position 0 — that's lowestSetBitIndex(N) halvings. Total = (popcount − 1) + trailingZeros.

A · Core idea

Count the moves directly from N's binary representation.

Why it matches the simulation. It's the same sequence of moves, just counted by structure instead of replayed — O(1) versus O(log N).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

N = 132 = 10000100

Interactive diagram

Bits to move count

popcount

Active call / nodeSupporting contextReturned stateNot active

popcount − 1 subtracts plus trailing-zeros halvings.

Final resultLouise

C · Code with teaching comments

solution.javaJava

Bit Formula — Popcount and Trailing Zeros (Optimal) — optimal

3 teaching notes

1
public String counterGame(long n) {
2
    int moves;
3
    // An initial 1 means zero moves; without this guard the formula still gives 0, but
4
    // the guard makes the rule explicit.
5
    if (n == 1) {
6
        moves = 0;
7
    } else {
8
        // popcount−1 subtracts to leave one bit, plus trailing zeros halvings to bring
9
        // it to 1.
10
        moves = (Long.bitCount(n) - 1) + Long.numberOfTrailingZeros(n);
11
    }
12
    // Parity of the move count names the winner — Louise on odd.
13
    return (moves % 2 == 1) ? "Louise" : "Richard";
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(1) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(1) time, O(1) space — A population count and a trailing-zero count are single built-ins (or O(word size) at worst). No loop over moves — constant time.

E · Edge cases and pitfalls6N = 1 — moves = 0 (even) → Richard, the immediate-win rule.Explore edge cases

Edge cases handled

N = 1moves = 0 (even) → Richard, the immediate-win rule.
N = 2 (power of 2)popcount 1, trailing 1 → moves = 0 + 1 = 1 (odd) → Louise; 2 → 1 in one halving.
N = 6popcount 2, trailing 1 → (2−1)+1 = 2 (even) → Richard, matching the simulation.

Pitfalls

Reversing the parity mapping (Louise on even instead of odd).
Using a 32-bit popcount/trailing-zero call on a value near 2⁶⁴ — use the 64-bit (Long) versions.
Counting the highest set bit instead of the lowest for the halving count.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String counterGame(long n) { int moves; if (n == 1) { moves = 0; } else {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Parity mapped to the wrong player

Louise moves first (turns 1, 3, 5…). If the total move count is odd, she made the last (winning) move. Swapping this reports the wrong winner.

Explore the code comparison

Don't write this

return (moves % 2 == 0) ? "Louise" : "Richard";

Write this instead

return (moves % 2 == 1) ? "Louise" : "Richard";

32-bit overflow on large N

N can be just under 2⁶⁴. A signed 32-bit int wraps around and corrupts both the power-of-two test and the move count.

Explore the code comparison

Don't write this

int n = readValue();           // overflows for N >= 2^31
while (n > 1) { ... }

Write this instead

long n = readValue();          // 64-bit; use unsigned-safe ops
while (n > 1) { ... }

Subtracting a power that's not strictly below N

The rule subtracts the largest power of 2 LESS than N. For a non-power-of-two that's its highest set bit; using N itself or a power ≥ N breaks the reduction.

Explore the code comparison

Don't write this

n -= 1 << n.bit_length()        # this is >= n

Write this instead

n -= 1 << (n.bit_length() - 1)  # highest set bit, < n

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Move count by bit structure → winner by parity

Code pattern to memorize

if N == 1: moves = 0
else: moves = (popcount(N) - 1) + lowestSetBitIndex(N)
return "Louise" if moves % 2 == 1 else "Richard"
# simulation form:
# while N > 1: if isPowerOf2(N): N >>= 1 else N -= highestPowerOf2BelowN; moves++

Rules to remember

1Power of two ⇔ a single set bit ⇔ `N & (N − 1) == 0`. Halving such a number shifts that one bit down by one position.
2When N is NOT a power of two, the largest power of 2 below N equals N's highest set bit, so subtracting it just clears that top bit.
3Therefore each subtract removes one high bit (popcount drops by 1) and each later halving moves the surviving lowest bit toward bit 0.
4Total moves = (popcount(N) − 1) subtracts to leave one bit, plus lowestSetBitIndex(N) halvings to bring it to bit 0.
5Louise moves first, so odd total moves → Louise wins, even → Richard. N == 1 means 0 moves → Richard wins immediately.

Use this pattern when

Alternating two-player game where the winner depends on the move count's parity
Operations that map cleanly to clearing or shifting bits
You can replace a simulation with a popcount / trailing-zero formula
Any 'halve if power of two, else subtract largest power of two' reduction

Choose another pattern when

Players have real choices that change the outcome → Sprague–Grundy / game DP, not a fixed move count
Operation set doesn't reduce to bit clears/shifts → simulate or model differently
You need the full move sequence, not just the winner → keep the simulation
N tiny and clarity matters more than speed → the simulation is plenty

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

←

Cipher

Continue · Next problem

Maximizing XOR