Bulb Switcher — Leetcode problem 319

Original Leetcode problem: https://leetcode.com/problems/bulb-switcher/

In this problem, we are given n light bulbs that are off initially. In the first round, all are switched to on. In the second round, every second bulb is toggled (to off), and in the third round, every third bulb is toggled, etc…until we reach n rounds. It asks for the number of bulbs on after n rounds.

The first (naive) solution I thought of was trying to simulate XOR on each round. Java code below:

class Solution {
    public int bulbSwitch(int n) {
        StringBuilder state = new StringBuilder();
        for (int i = 0; i < n; i++) {
            state.append('0');
        }
        for (int i = 1; i <= n; i++) {
            toggle(state, i, n);
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (state.charAt(i) == '1') {
                count++;
            }
        }
        return count;
    }
    
    private void toggle(StringBuilder state, int gap, int n) {
        if (gap == n) {
            char ch = state.charAt(n - 1);
            if (ch == '0') {
                state.setCharAt(n - 1, '1');
            } else {
                state.setCharAt(n - 1, '0');
            }
            return;
        }
        for (int i = 0; i < n; i++) {
            if ((i + 1) % gap == 0) {
                char ch = state.charAt(i);
                if (ch == '0') {
                    state.setCharAt(i, '1');
                } else {
                    state.setCharAt(i, '0');
                }
            }
        }
    }
}

Perhaps not surprisingly, this gets Time Limited Exceeded exception upon submission, since it does loop n times every n…

Next, I thought there must be some sort of formula for calculating the number directly. I tried drawing diagrams of n x n circles and toggling them on paper to see if I could find some pattern and writing out which ranges of numbers had the same number of lit bulbs in the end and grouping them in buckets.

Bulb Remaining: 
1: n = 1, 2, 3
2: 4, 5, 6, 7, 8
3: 9...15
4: 16...24
5: 25...35
6: 36...48

with the aid of my naive implementation to figure out the borderlines between buckets. The ending numbers do seem to be in a pattern of having a difference of 5, 7, 9, 11, and so on, but that led me nowhere.

So I finally decided to check the discuss section. And the answer was as simple as…

wait for it…

public int bulbSwitch(int n) {
    return (int)Math.sqrt(n);
}

square root of n (rounded down)!

The reason was that I had not noticed that when we were writing the buckets of ranges, each number at the beginning of the bucket was a perfect square:

1, 4, 9, 16, 25...

Also, when I was drawing the n x n diagrams of circles, I could draw perfect squares for each n (since it is n x n).

I personally would find this the more intuitive explanation for this clever one line solution :)