https://leetcode.com/problems/bulb-switcher/description/
There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds.
Example:
Input: 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After first round, the three bulbs are [on, on, on]. After second round, the three bulbs are [on, off, on]. After third round, the three bulbs are [on, off, off]. So you should return 1, because there is only one bulb is on.
中文翻譯:
有N個電燈泡(搭配N個開關)，一開始都是暗的[off,off,off,off...]。
第一輪，我每一個開關都去按，所以變成[on,on,on,on,...]。
第二輪，我每二個開關才去按，所以變 [on,off,on,off,..]。
第三輪，我每三個開關才去按，所以變 [on,off,off,off...]。
第四輪，我每四個開關才去按，所以變 [on,off,off,on...]。
請問N輪之後，剩幾個亮的?
Find those who is perfect square and smaller than or equal to N.
Let me explain the reason step by step.
1.The bulbs, that been toggled for odd times, will become "on".
Since the initial state is "off", it's obviously that you can turn "on" a bulb by only toggled it odd times.
2.The bulbs, who's index is a perfect square, will be toggled for odd times.
Let me explain this by step A and B.
A.Number of Toggling = Number of factors.
For bulb with index k, how many times will it be toggled?
The answer is "the number of k's factors".
e.g.
Bulb with index 1 will be toggled at round 1. <- 1 factor, toggled 1 times
Bulb with index 2 will be toggled at round 1 and 2. <-2 factors, toggled 2 times
Bulb with index 3 will be toggled at round 1 and 3. <-2 factors, toggled 2 times
Bulb with index 4 will be toggled at round 1 and 2 and 4. <-3 factors, toggled 3 times
B. K's number of factor is odd, if and only if K is a perfect square.
Let's say if K has a factor 'a', that means it must have another factor 'b', which makes a*b=K.
So basically the factors of an positive integer 'K' will appear in the form of "pair" such as (a,b).
e.g.
6's factors are 1,2,3,6. There are 2 pairs (1,6), (2,3). And the products are both 6.15's factors are 1,3,5,15. There are 2 pairs (1,15), (3,5). And the products are both 15.
Since the factors appear in the form of "pair", the number of factors must be even.
This conclusion is mostly true, except for one condition : "K is a perfect square".
If K is a perfect square, there exist a factor 's', such that s*s = K.
's' is the only factor that is not appear in form of "pair".
It makes number of factors of K being odd.
3.Find those who is perfect square and smaller than or equal to N.
Combining conclusion 1 and 2, we will find the solution of this problem is :Finding the those bulbs who are perfect square, they have odd number of factors.
They will be toggled odd times. They will be turned "on".
Let's write code.
class Solution {
public:
int bulbSwitch(int n) {
int ans=0;
//Find those who is perfect square and smaller than or equal to N.
for(int a=1;a*a<=n;a++){
ans++;
}
return ans;
}
};
There is an even quicker way to find how many perfect squares between 1 and N.
The answer is : the integer part of square root of N.
Because, if square root(K) is an integer, K is a perfect square.
If you calculate square root for 1~N,
all results will located between square_root(1)~square_root(N), which is 1~square_root(N).
And the number of integer between 1~square root(N) is the integer part of square root(N).
class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n);
}
};
