319. Bulb Switcher

For each bulb at position i, it is only switched if the round r divides i. For any integer, the divisor comes in pairs, for example, 8 has divisor pairs of (1, 8), (2, 4) and eventually, bulb 8 will be off. Another example, 16 has divisor pairs (1, 16), (2, 8), (4, 4) and eventually bulb 16 will be on. So bulb i will be on if and only if when i has an integer square root. So the problem becomes how many such integers in [1, n]. Since sqrt(n) is largest square root and 1 is the smallest square root, so you have total sqrt(n) square roots in [1, n].

1:  class Solution {  
2:  public:  
3:    int bulbSwitch(int n) {  
4:      return sqrt(n);  
5:    }  
6:  };