# 100 Doors Puzzle: Parity, Perfect Squares, Divisor Counts

Source: https://www.techinterview.org/post/3233459720/100-doors-to-be-painted/
Updated: 2026-04-27 · techinterview.org

## The 100 Doors Puzzle: Parity, Perfect Squares, and Why Divisor Counts Matter

The 100 doors puzzle is a beautiful number-theory interview question. The setup: 100 doors, all initially closed. 100 people walk past. Person k toggles every kth door. After all 100 people have walked past, which doors are open? The answer involves divisor counts and reveals a deep connection to perfect squares. This guide covers the puzzle, the elegant solution, and the variations interviewers ask.

## Problem Statement

Doors 1 through 100, all initially closed.

- Person 1 toggles every door (every 1st door): doors 1, 2, 3, ..., 100.

- Person 2 toggles every 2nd door: doors 2, 4, 6, ..., 100.

- Person 3 toggles every 3rd door: doors 3, 6, 9, ..., 99.

- ...

- Person 100 toggles every 100th door: door 100.

"Toggle" means flip the state — closed becomes open, open becomes closed. After all 100 people have walked past, which doors are open?

## The Naive Approach

Simulate. For each door d, count how many people toggle it; if odd, it ends open; if even, it ends closed.


```
def doors_after_toggling(n: int) -> list[bool]:
    """Simulate the puzzle. Returns list of door states; True = open."""
    doors = [False] * (n + 1)  # 1-indexed
    for person in range(1, n + 1):
        for door in range(person, n + 1, person):
            doors[door] = not doors[door]
    return doors[1:]


# Test
result = doors_after_toggling(100)
open_doors = [i + 1 for i, state in enumerate(result) if state]
print(open_doors)  # [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
```


The output is the perfect squares from 1 to 100. There are 10 of them.

**Complexity:** O(n × n) for the simulation. Acceptable for n = 100; impractical for very large n. Strong candidates derive the result analytically.

## The Elegant Answer: Doors at Perfect Squares Are Open

Door d is toggled by person k if and only if k divides d. So door d is toggled exactly *τ(d)* times, where τ(d) is the number of divisors of d.

Door d ends open iff τ(d) is odd.

For most numbers, divisors come in pairs: if k divides d, then d/k also divides d. So τ(d) is typically even. The exception: when k = d/k, i.e., k² = d, i.e., d is a perfect square. In that case, k is paired with itself, contributing only one to the divisor count instead of two.

**Therefore, τ(d) is odd if and only if d is a perfect square.**

For n = 100, the perfect squares are 1, 4, 9, 16, 25, 36, 49, 64, 81, 100. Ten doors end open.


```
def perfect_square_doors(n: int) -> list[int]:
    """Return doors that end open (perfect squares ≤ n)."""
    result = []
    k = 1
    while k * k <= n:
        result.append(k * k)
        k += 1
    return result


print(perfect_square_doors(100))
# [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
```


**Complexity:** O(√n) time, O(√n) space (for the result). Massively faster than the simulation.

## Why Perfect Squares Have Odd Divisor Counts

For any integer d, the divisors come in pairs (k, d/k). Each divisor k corresponds to its complement d/k. The pair contributes 2 to τ(d).

The exception is when k = d/k, which requires k² = d. This means d is a perfect square; the divisor k = √d pairs with itself, contributing 1 instead of 2.

For non-square d: all divisor pairs are distinct → τ(d) is even.

For square d: one divisor pairs with itself; rest pair distinctly → τ(d) is odd.

Verification:

- d = 6: divisors {1, 2, 3, 6}. τ(6) = 4. Even. Door 6 ends closed.

- d = 9 = 3²: divisors {1, 3, 9}. τ(9) = 3. Odd. Door 9 ends open.

- d = 16 = 4²: divisors {1, 2, 4, 8, 16}. τ(16) = 5. Odd. Door 16 ends open.

## Common Variations

### K people instead of N

Only k people walk past (k < n). Door d is toggled τ(d, k) times, where τ(d, k) is the number of divisors of d that are at most k. Doors open iff this count is odd. The "perfect square" answer no longer applies cleanly — now it depends on which divisors fall within k.

### Doors initially open instead of closed

Same toggling logic, just inverted. Doors initially open end closed iff toggled an odd number of times → perfect squares end closed; non-squares end open.

### Bidirectional walks

Each person walks past twice (or N times). The toggle count multiplies, but parity changes only when the multiplier is odd. Most "k passes" variants reduce to a single equivalent puzzle.

### Mod-3 or mod-K state instead of toggle

"Each visit increments the door's counter; door is open iff counter ≥ K." Different problem; the divisor-count insight no longer applies directly.

## What Interviewers Test

- Recognize that the simulation's answer (perfect squares) suggests a deeper structure

- Connect "door d toggled if person k divides d" to divisor counts

- Realize divisors pair except for perfect squares

- Conclude: doors at perfect squares end open

Strong candidates derive the answer without simulation, then verify on small cases. Weaker candidates simulate and stop without seeing the structure.

## Frequently Asked Questions

### What's the expected interview answer?

  Doors at perfect squares (1, 4, 9, 16, 25, 36, 49, 64, 81, 100 for n = 100) end open. Walk through the reasoning: door d is toggled τ(d) times; τ(d) is odd iff d is a perfect square; therefore door d is open iff d is a perfect square. Strong candidates explain why divisors pair (and why perfect squares are the exception).

### How do I derive the answer without simulating?

  Start by asking: for door d, who toggles it? Person k does iff k divides d. So door d is toggled exactly τ(d) times. Door d ends open iff τ(d) is odd. When is τ(d) odd? When d is a perfect square. Done. The whole derivation takes 60 seconds with practice.

### What's the connection to number theory?

  τ(d) (the divisor function) is one of the most-studied functions in number theory. The fact that τ(d) is odd iff d is a perfect square is a foundational result, used in many other problems. The 100 doors puzzle is often a candidate's first encounter with this result.

### How does this generalize?

  For any K (not necessarily n), if person k toggles every kth door (k = 1 to K), then door d ends open iff (number of divisors of d in [1, K]) is odd. For K = n, this simplifies to "d is a perfect square." For K < n, the condition is more complex; some divisors of d may exceed K.

### Why is this puzzle so loved by interviewers?

  It looks like simulation but reveals a deep number-theory insight. Candidates who simulate get the right list of doors but miss the structural reason. Candidates who reason analytically see the perfect-squares pattern and explain why. The gap between the two kinds of candidates is what the interview tests.

See also: [Bridge Crossing Puzzle](/post/3233459680/three-people-on-a-weak-bridge/) • [Fruit Jar Labeling Puzzle](/post/3233459687/fruit-jar-problem/) • [Power of Two Check](/post/3233459629/check-if-a-number-is-power-of-two/)