Cracking The Coding Interview Together – Problem 6.9: 100 Lockers

We have all been there. You are sitting in an interview, expecting a standard dynamic programming or graph traversal question, when the interviewer throws a classic mathematical brain teaser your way: The 100 Lockers Problem. At first glance, it feels like a trick. Your immediate instinct as a developer might be to spin up a quick array, write a nested loop, and simulate the entire process. It is a natural reaction—we are builders, and we like to see things run.

But as senior engineers, we must resist the urge to immediately write code without understanding the underlying system. Brute-forcing a simulation is a trap. It shows that we can write loops, but it does not show that we can optimize, analyze, or find elegant mathematical shortcuts. Today, we are going to tackle this problem together. We will start by analyzing the core conflict, transition from a naive simulation to an incredibly elegant mathematical proof, and write production-ready Java code that demonstrates both approaches. Our goal is to understand not just which lockers remain open, but the deep mathematical reason why they do.

Problem Statement

The problem is defined as follows:

There are 100 closed lockers in a hallway. A man walks down the hallway and performs 100 passes. With each pass, he toggles the state of certain lockers (if a locker is closed, he opens it; if it is open, he closes it) according to the following rules:

• Pass 1: He toggles every locker that is a multiple of 1 (i.e., locker 1, 2, 3, ..., 100).
• Pass 2: He toggles every locker that is a multiple of 2 (i.e., locker 2, 4, 6, ..., 100).
• Pass 3: He toggles every locker that is a multiple of 3 (i.e., locker 3, 6, 9, ..., 99).
• ...
• Pass $i$: He toggles every locker that is a multiple of $i$.
• ...
• Pass 100: He toggles locker 100.

After all 100 passes are complete, which lockers remain open?

Analyze the Problem Together

Let's break down the mechanics of this problem. A locker's state is binary: it is either Closed (0) or Open (1). Every locker starts in the Closed state.

When does a locker get toggled? Locker n is toggled on pass i$if and only if i is a factor (divisor) of n For example, let's look at locker 12. The factors of 12 are 1, 2, 3, 4, 6, and 12. This means locker 12 will be toggled on passes 1, 2, 3, 4, 6, and 12. Let's trace its state transitions:

• Initial: Closed
• Pass 1: Open
• Pass 2: Closed
• Pass 3: Open
• Pass 4: Closed
• Pass 6: Open
• Pass 12: Closed

Locker 12 ends up Closed. Why? Because it was toggled exactly 6 times. Since 6 is an even number, the locker returned to its initial state.

This brings us to our first major realization: A locker will end up OPEN if and only if it is toggled an odd number of times.

So, the question "Which lockers remain open?" is mathematically equivalent to "Which numbers between 1 and 100 have an odd number of factors?"

Let's analyze how factors pair up. For any number n, if a is a factor of n, then there must exist some b such that a \times b = n. This means factors almost always come in pairs. For example, the factors of 12 pair up as: (1, 12), (2, 6), and (3, 4). Because they pair up, the total count of factors is usually even.

When does a factor not have a distinct partner? This only happens when a factor is paired with itself! That is, a \times a = n, which means a = \sqrt{n}. This is only possible if n is a perfect square.

Let's look at a perfect square, like 16. Its factors are 1, 2, 4, 8, and 16. The pairs are (1, 16), (2, 8), and (4, 4). Since 4 is paired with itself, we only count it once in our set of unique factors: {1, 2, 4, 8, 16}. The total number of factors is 5, which is odd! Therefore, locker 16 will end up Open.

Let's summarize this with a comparative table:

Questions for the Interviewer

Even when a problem seems straightforward, a senior engineer always asks clarifying questions to demonstrate attention to detail, scale, and edge cases. Here are three questions we should ask:

1. "Does the number of lockers scale dynamically?" - If $N$ can be up to $10^9$, a simulation approach will completely fail due to time and memory limits. Knowing the scale helps us choose between a simulation and a direct mathematical calculation.
2. "Are the locker numbers 1-indexed or 0-indexed?" - In mathematical puzzles, we typically use 1-indexing (lockers 1 to 100). In code, we must map this carefully to avoid off-by-one errors.
3. "What should the system return?" - Do we need to return the list of open locker numbers, the count of open lockers, or a boolean array representing the state of all lockers?

Think About the Solution

We will design a solution that provides two distinct implementations to show our versatility:

1. The Simulation Approach: This is our baseline. We will use a boolean array of size $N + 1$ to represent the lockers. We will run a nested loop to simulate the toggling process. This is great for verifying our mathematical hypothesis and writing unit tests.
2. The Optimized Mathematical Approach: Since we proved that only perfect squares remain open, we can directly generate all perfect squares less than or equal to $N$. For $N = 100$, the perfect squares are $1^2, 2^2, 3^2, ..., 10^2$, which correspond to lockers 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. This approach bypasses the simulation entirely.

Let's handle edge cases: if $N \le 0$, we should return an empty list. If $N = 1$, we should return a list containing just `[1]`.

Write Code and Explain

Here is the complete, production-ready Java implementation containing both the simulation and the optimized mathematical approach.

package com.thedevlearnings.lockers;

import java.util.ArrayList;
import java.util.List;

public class LockerSolver {

    /**
     * Simulates the locker toggling process step-by-step.
     * Time Complexity: O(N^2)
     * Space Complexity: O(N)
     */
    public static List<Integer> solveBySimulation(int n) {
        if (n <= 0) {
            return new ArrayList<>();
        }

        // Use a boolean array where index i represents locker i.
        // false = closed, true = open.
        // We use size n + 1 to keep it 1-indexed for clarity.
        boolean[] lockers = new boolean[n + 1];

        // Outer loop: represent each pass from 1 to n
        for (int pass = 1; pass <= n; pass++) {
            // Inner loop: toggle every multiple of the current pass
            for (int locker = pass; locker <= n; locker += pass) {
                lockers[locker] = !lockers[locker];
            }
        }

        // Collect all lockers that remain open
        List<Integer> openLockers = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (lockers[i]) {
                openLockers.add(i);
            }
        }

        return openLockers;
    }

    /**
     * Solves the problem instantly using mathematical deduction.
     * Only perfect squares have an odd number of factors and remain open.
     * Time Complexity: O(sqrt(N))
     * Space Complexity: O(1) auxiliary space
     */
    public static List<Integer> solveOptimized(int n) {
        List<Integer> openLockers = new ArrayList<>();
        if (n <= 0) {
            return openLockers;
        }

        // Generate perfect squares: 1, 4, 9, 16, ... up to n
        for (int i = 1; i * i <= n; i++) {
            openLockers.add(i * i);
        }

        return openLockers;
    }

    public static void main(String[] args) {
        int totalLockers = 100;
        
        System.out.println("--- Running Simulation Approach ---");
        List<Integer> simulationResult = solveBySimulation(totalLockers);
        System.out.println("Open Lockers: " + simulationResult);

        System.out.println("\n--- Running Optimized Approach ---");
        List<Integer> optimizedResult = solveOptimized(totalLockers);
        System.out.println("Open Lockers: " + optimizedResult);
        
        // Verify correctness
        boolean match = simulationResult.equals(optimizedResult);
        System.out.println("\nDo both methods match? " + (match ? "YES" : "NO"));
    }
}

Code Walkthrough

Let's trace how the optimized method works. The loop condition is `i * i <= n`. We start with `i = 1`. Since $1 \times 1 = 1 \le 100$, we add 1 to our list. Next, `i = 2`, $2 \times 2 = 4 \le 100$, we add 4. This continues until `i = 10`, where $10 \times 10 = 100 \le 100$, so we add 100. On the next iteration, `i = 11`, $11 \times 11 = 121 > 100$, so the loop terminates. We have successfully generated all perfect squares up to 100 in exactly 10 iterations!

Time & Space Complexity

Let's analyze the performance of both approaches to highlight why the mathematical optimization is so powerful.

Simulation Approach

• Time Complexity: $O(N \log N)$ or $O(N^2)$ depending on the exact loop bounds. The inner loop runs $N/1 + N/2 + N/3 + ... + N/N$ times. This is a harmonic series, which sums to $N \ln N$. Thus, the time complexity is $O(N \log N)$. For $N = 100$, this is negligible, but for $N = 10^7$, it becomes highly inefficient.
• Space Complexity: $O(N)$ to store the state of the boolean array.

Optimized Approach

• Time Complexity: $O(\sqrt{N})$. The loop runs exactly $\lfloor\sqrt{N}\rfloor$ times. For $N = 100$, it runs 10 times. For $N = 10^8$, it runs only 10,000 times! If we only needed to return the count of open lockers instead of the list, we could do it in $O(1)$ time using `(int) Math.sqrt(n)`!
• Space Complexity: $O(1)$ auxiliary space (excluding the space required to store the output list).

Why This Problem Matters (The Senior Perspective)

You might ask: "When will I ever need to toggle lockers in a real production system?" The answer is never. However, the core engineering patterns behind this problem are highly relevant to real-world software architecture:

1. Mathematical Reduction over Brute Force: In production, we often face tasks that look like they require heavy computation. For example, calculating analytics over millions of database rows. A junior engineer might write a complex batch job that processes every row. A senior engineer looks for mathematical shortcuts, pre-aggregations, or analytical formulas that can reduce an $O(N)$ or $O(N^2)$ operation to $O(1)$ or $O(\log N)$.
2. State Machine Design: The toggling of a locker is a classic state machine transition. Understanding how inputs (divisors) affect state transitions is critical when designing complex workflows, such as order processing systems, user subscription states, or distributed consensus protocols.
3. Scale and Resource Management: If this were a real-world system where $N$ could scale to billions, the simulation approach would cause OutOfMemory (OOM) errors and CPU throttling. Recognizing scale limits and designing algorithms that run in $O(1)$ space is what separates senior architects from junior developers.

Final Thoughts

The 100 Lockers problem is a beautiful reminder that computer science is deeply rooted in mathematics. By taking a step back, analyzing the patterns of factors, and identifying the unique properties of perfect squares, we transformed a slow, memory-intensive simulation into an incredibly fast, elegant, and optimal solution.

Next time you face a problem that seems to require nested loops and heavy state tracking, ask yourself: Is there an underlying mathematical pattern I can exploit here?

Keep coding, keep optimizing, and we will see you in the next post!