# Math solution..

• ``````int bulbSwitch(int n) {
return sqrt(n);
}
``````

A bulb ends up on iff it is switched an odd number of times.

Call them bulb 1 to bulb n. Bulb i is switched in round d if and only if d divides i. So bulb i ends up on if and only if it has an odd number of divisors.

Divisors come in pairs, like i=12 has divisors 1 and 12, 2 and 6, and 3 and 4. Except when i is a square, like 36 has divisors 1 and 36, 2 and 18, 3 and 12, 4 and 9, and double divisor 6. So bulb i ends up on if and only if i is a square.

So just count the square numbers.

Let R = int(sqrt(n)). That's the root of the largest square in the range [1,n]. And 1 is the smallest root. So you have the roots from 1 to R, that's R roots. Which correspond to the R squares. So int(sqrt(n)) is the answer. (C++ does the conversion to int automatically, because of the specified return type).

• Very brilliant!

• omg! orz....

• can't believe it!

• damn it, it's so smart

• the parameter 'i' starts at 0

• @King_YL No, it starts at 1. Sorry if that was unclear.

• 666666666666

• damn ! So smart!

• Can you please explain how you get from "So just count the square numbers." to `sqrt`?

• @TWiStErRob
I guess that's indeed a little gap that I just jumped intuitively. Well, `sqrt` gives you the root of the largest square in the range [1,n]. And 1 is the smallest root. So you have the roots from 1 to sqrt, that's sqrt many roots. Which correspond to the sqrt many squares.

• This post is deleted!

• This post is deleted!

• what the CS is

• Bravo!!!!!!!!!!!!!!!!!!!!!!!!

• Your explanation is quite clear. Thanks man.

• This post is deleted!

• I think until the divisor part and then I tried to find ways to imimic the finding process. I didn't expect such a short answer. Thank you!

• hi Lilei, long time no see. How are u?

• I couldn't hold my tears.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.