Leetcode punch in diary day 01

leetcode 319 Bulb switch

Initially there is n One bulb is off . The first round , You'll turn on all the lights . The next round , You will turn off one light bulb every two .

The third round , You switch one light bulb every three light bulbs （ namely , Open to close , Turn off to turn on ）. The first i round , Every time you i A light bulb is a switch that switches one light bulb . Until the first n round , You just need to switch the last light bulb .

Find out and return to n How many light bulbs are there behind the wheel .

 Input ：n = 3
 Output ：1 
 explain ：
 At the beginning ,  Lamp status  [ close ,  close ,  close ].
 After the first round ,  Lamp status  [ Turn on ,  Turn on ,  Turn on ].
 After the second round ,  Lamp status  [ Turn on ,  close ,  Turn on ].
 After the third round ,  Lamp status  [ Turn on ,  close ,  close ]. 

 You should go back  1, Because only one bulb is still on .


 Input ：n = 0
 Output ：0

The first time I saw this question , The idea is to simulate the whole process of bulb switching , But finally I saw the solution , I'm a fool .

Mathematical methods ：
therefore , For the first k A light bulb , The number of times it is switched is exactly k The approximate number of . If k There are even divisors , So finally, the third k The state of each bulb is dark ; If k There are odd divisors , So finally, the third k The state of each bulb is on .

about k for , If it has a divisor x, Then there must be a divisor k/x, So just be x^2 It's not equal to k, Divisors are 「 Pair 」 The emergence of . This means that , Only when k yes 「 Complete square 」 when , It will have odd divisors , Otherwise, there must be even divisors .

So we just need to find out 1, 2, 3,⋯,n The number of complete squares in , The answer is sqrt(n);

The little detail is , In order to avoid accuracy problems , It can be changed to sqrt(n + 0.5); Make sure the rounding down range is correct .
​