Katkat
Back

Count Open Lockers After 100 Rounds

TekionSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenStatistics & Math

Last updated

This problem tests mathematical reasoning and pattern recognition, specifically the relationship between integer divisors and toggling operations.

The Locker Problem

There are 100 lockers in a hallway, numbered 1 to 100. Initially, all of them are closed. You perform 100 rounds of operations. In round 1, you toggle every locker (closed becomes open, open becomes closed). In round 2, you toggle every second locker (2, 4, 6, ...). In round 3, you toggle every third locker (3, 6, 9, ...), and so on, until in round 100, you toggle only the 100th locker.

Determine how many lockers are open after all 100 rounds are completed and identify which specific locker numbers remain open.

Requirements

  • Provide the total count of open lockers.
  • Explain the mathematical reasoning behind why certain lockers remain open.

Example

Consider a smaller scale of 5 lockers:

  • Initially: [C, C, C, C, C]
  • Round 1: [O, O, O, O, O]
  • Round 2: [O, C, O, C, O]
  • Round 3: [O, C, C, C, O]
  • Round 4: [O, C, C, O, O]
  • Round 5: [O, C, C, O, C]
  • Final state: Lockers 1 and 4 are open. Count = 2.

Edge Cases

  • Consider if the number of lockers was 1 or a prime number.

Hints

Hint 1

A locker is toggled in round 'k' if and only if 'k' is a divisor of the locker number.

Hint 2

A locker ends up in the 'open' state if it has been toggled an odd number of times.

Hint 3

Think about the properties of the number of divisors an integer has; for which integers is the total count of divisors odd?

Follow-up questions

  • How would your approach change if you were asked to determine the state of the 500th locker specifically?
  • If you performed this process with 'N' lockers, what is the formula to calculate the number of open lockers?
  • What would happen if, instead of starting closed, every 3rd locker started as open?