Bulb toggling is one of the famous puzzles asked in various interviews. The problem statement is as follows.

LeetCode Problem: 319

There are ‘n’ bulbs that are initially OFF. You have to play a game in which there are n rounds.

In the first round, you turn ON all the bulbs.

In the second round, you toggle every second bulb (turning ON if it's OFF or turning OFF if it's ON).

In the third round, you toggle every third bulb.
.
.
.
For the ith round, you toggle every i bulb.

For the nth round, you toggle the nth bulb (i.e. last bulb).

Return the number of bulbs that are ON after n rounds.

1. Bruteforce Approach

The naive approach is to take a boolean array of size n+1 that will maintain the state of every bulb after each round (0 : "OFF" and 1 : "ON"). We then run two nested loops, the outer loop will run n times and it will signify the n rounds of the game, and for its ith iteration, the inner loop will run, toggling the value of every ith element in the boolean array.

After the nth round, we could finally traverse the boolean array and count the number of 1s in it.

#include <iostream>
using namespace std;

int bulbSwitch(int n) {
    bool bulb[n+1] = {0};
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            bulb[j] = !bulb[j];
        }
    }
    int count = 0;
    for (int i = 1; i <= n; i++)
        if (bulb[i] == 1)
            count++;

    return count;
}

int main() {
    int n = 4;
    cout << bulbSwitch(n);

    return 0;
}

2. Efficient Approach

Initially all the n bulbs will be OFF, so if any bulb is toggled even number of times, then it will remain OFF.

Let us try to understand the above statement in depth and extract the logic to solve this problem efficiently.

Consider we have 4 bulbs and thereby we need to calculate the states of the bulbs after 4 rounds.

if n = 4
        initially: 0 0 0 0
        i = 1:     1 1 1 1
        i = 2:     1 0 1 0
        i = 3:     1 0 0 0
        i = 4:     1 0 0 1

So after 4 rounds, 2 bulbs are ON.

Analysis of bulb number vs iteration number:

bulb number: iteration number when it is toggled
        1 : 1             
        2 : 1, 2
        3 : 1, 3
        4 : 1, 2, 4

Note: A bulb with be ON after n rounds, if it is toggled odd number of times.

        1 : 1     (odd no. of factors) -> Finally ON 
        2 : 1, 2  (even no. of factors) -> Finally OFF
        3 : 1, 3  (even no. of factors) -> Finally OFF
        4 : 1, 2, 4 (odd no. of factors) -> Finally ON

So, our task is to find the count of numbers from 1 to n, that have odd number of factors. By now, you must have figured out the logic, however, if it hasn't clicked yet, don't worry. More detailed explanation on the way 🔥. Let's try to work our few numbers and unravel the hidden patterns.

Factors of 1 -> 1 (odd number of factors)
Factors of 8 -> 1, 2, 4, 8 (even number of factors)
Factors of 9 -> 1, 3, 9 (odd number of factors)
Factors of 16 -> 1, 2, 4, 8, 16 (odd number of factors)

Every number >= 1 has at least 2 factors, 1 and the number itself. In simple words, to get an odd number of factors, we need to find a factor which does not occur in pair ie. the factor has an even power. So, we could simply find the count of perfect squares from 1 to n.

Implementation: Version-1

int bulbSwitch(int n) {
        int count = 0, i = 1;
        while(i * i <= n) {
            count++;
            i++;
        }
        return count;
    }

We can observe that the variables count and i are increment equal number of times. Here the value of i is the square root of n.

Below is the 1 line solution of the Bulb Toggling problem.

Implementation: Version-2

int bulbSwitch(int n) {
        return floor(sqrt(n));
    }

Hope you enjoyed this article and feel free to connect with me on LinkedIn and github.