Back to Interview Games

100 Lights Toggle

LogicEasy
10 min
15 pts

Description

Lights start off. Toggle every ith light on pass i. How many are on at the end?

Game Rules

100 lights are initially off. On pass i, toggle every ith light (i.e., lights i, 2i, 3i, ...). After 100 passes, how many lights are on?

Examples

Light 1: toggled once (on)

Light 4: toggled on passes 1, 2, 4 (off)

Light 9: toggled on passes 1, 3, 9 (on)

Only perfect squares are toggled odd times

Hints

  • Count how many times each light is toggled

  • Think about divisors

Solution (Click to reveal)

Only lights with perfect square numbers (1, 4, 9, 16, 25, 36, 49, 64, 81, 100) are on. Answer: 10 lights.

Back