text: Math solution.. | LeetCode Discuss
  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).
  ulyooo
  omg! orz....
  zkwangchao
  damn it, it's so smart
  the parameter 'i' starts at 0
  @King_YL No, it starts at 1. Sorry if that was unclear.
  damn ! So smart!
  Can you please explain how you get from "So just count the square numbers." to sqrt?
  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.
  what the CS is
  lileiforhanmeimei
  Your explanation is quite clear. Thanks man.
  zhangzhp
  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!