# Bulb Switcher Solutions in C++

Number 319

Difficulty Medium

Acceptance 45.3%

Link LeetCode

Other languages —

## Solutions

### C++ solution by haoel/leetcode

// Source : https://leetcode.com/problems/bulb-switcher/// Author : Calinescu Valentin, Hao Chen// Date : 2015-12-28/* Solution* --------** We know,* - if a bulb can be switched to ON eventually, it must be switched by ODD times* - Otherwise, if a bulb has been switched by EVEN times, it will be OFF eventually.* So,* - If bulb `i` ends up ON if and only if `i` has an ODD numbers of divisors.* And we know,* - the divisors come in pairs. for example:* 12 - [1,12] [2,6] [3,4] [6,2] [12,1] (the 12th bulb would be switched by 1,2,3,4,6,12)* - the pairs means almost all of the numbers are switched by EVEN times.** But we have a special case - square numbers* - A square number must have a divisors pair with same number. such as 4 - [2,2], 9 - [3,3]* - So, a square number has a ODD numbers of divisors.** At last, we figure out the solution is:** Count the number of the squre numbers!!*/class Solution {public:int bulbSwitch(int n) {int cnt = 0;for (int i=1; i*i<=n; i++) {cnt++;}return cnt;}};/** Solution 1 - O(1)* =========** We notice that for every light bulb on position i there will be one toggle for every* one of its divisors, given that you toggle all of the multiples of one number. The* total number of toggles is irrelevant, because there are only 2 possible positions(on,* off). We quickly find that 2 toggles cancel each other so given that the start position* is always off a light bulb will be in if it has been toggled an odd number of times.* The only integers with an odd number of divisors are perfect squares(because the square* root only appears once, not like the other divisors that form pairs). The problem comes* down to finding the number of perfect squares <= n. That number is the integer part of* the square root of n.**/class Solution {public:int bulbSwitch(int n) {return (int)sqrt(n);}};

### C++ solution by liuyubobobo/Play-Leetcode

/// Source : https://leetcode.com/problems/bulb-switcher/description//// Author : liuyubobobo/// Time : 2017-12-01#include <iostream>#include <cassert>using namespace std;/// For every number, see whether the divisor number is odd/// Time Complexity: O(n*sqrt(n))/// Space Complexity: O(1)////// Time Limit Exceed!!!class Solution {public:int bulbSwitch(int n) {assert(n >= 0);if(n <= 1)return n;int count = 1;for(int i = 2 ; i <= n ; i ++)if(divisorNumber(i) % 2 == 1)count += 1;return count;}private:int divisorNumber(int x){int ret = 0;for(int i = 1 ; i * i <= x ; i ++)if(x % i == 0){ret += 1;if(x / i != i)ret += 1;}return ret;}};int main() {cout << Solution().bulbSwitch(2) << endl;cout << Solution().bulbSwitch(3) << endl;return 0;}

### C++ solution by liuyubobobo/Play-Leetcode

/// Source : https://leetcode.com/problems/bulb-switcher/description//// Author : liuyubobobo/// Time : 2017-12-01#include <iostream>#include <cmath>#include <cassert>using namespace std;/// Only square number have odd divisor number!/// Time Complexity: O(1)/// Space Complexity: O(1)class Solution {public:int bulbSwitch(int n) {assert(n >= 0);return (int)sqrt(n);}};int main() {cout << Solution().bulbSwitch(2) << endl;cout << Solution().bulbSwitch(3) << endl;return 0;}