Bulb Switcher

Problem Statement

The bulb toggling puzzle consists of n bulbs lined up in a row, all initially turned off. The state of these bulbs is altered over a series of rounds, specifically n rounds in total. Each round, i, involves toggling the state of every ith bulb. A bulb's state is toggled by switching it from off to on or from on to off. Thus, for a given round i:

1. First round: every bulb is toggled (all bulbs turn on).
2. Second round: every second bulb is toggled (i.e., bulbs 2, 4, 6, …).
3. Third round: every third bulb is toggled (i.e., bulbs 3, 6, 9, …).
4. This process continues up to the nth round where only the nth bulb is toggled.

The challenge is to determine how many bulbs are left in the "on" position after all n rounds are completed.

Examples

Example 1

Input:

n = 3

Output:

1

Explanation:

At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off].
So you should return 1 because there is only one bulb is on.

Example 2

Input:

n = 0

Output:

0

Example 3

Input:

n = 1

Output:

1

Constraints

• 0 <= n <= 109

Approach and Intuition

The pattern of bulbs being toggled in multiple rounds is quite systematic, leading us to some interesting observations particularly about the factors of numbers:

• In every round i, the ith bulb's status is toggled.
• For any bulb j, it will be toggled for each divisor it has. For example, bulb 12 is toggled in rounds 1, 2, 3, 4, 6, and 12.
• Bulbs that are toggled an odd number of times will end up being on, and those toggled an even number of times will be off.

Observing patterns in factors:

• A bulb ends up on only if it has an odd number of total divisors. The numbers with an odd number of divisors are perfect squares. This is because divisors usually come in pairs, except when the number is a perfect square.

Consequently:

• The number of bulbs that remain on after all rounds can be determined by counting how many numbers up to n are perfect squares.

Given this understanding:

1. To find how many bulbs are on, identify all numbers up to n that are perfect squares. The count of these perfect squares gives the answer.
2. Mathematically, the count of perfect squares up to n is the integer part of the square root of n.

Thus, the problem simplifies to calculating how many perfect squares exist up to n, which can be done efficiently without simulating all the rounds.

Solutions

class Solution {
public:
    int switchBulbs(int bulbs) {
        return sqrt(bulbs);
    }
};