319. Bulb Switcher (Medium)
https://leetcode.com/problems/bulb-switcher/
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.
Solutions
class Solution {
public int bulbSwitch(int n) {
// 1st bulb flipped 1 time
// 2nd bulb flipped 2 times
// 3rd bulb flipped 2 times
// 4th bulb flipped 3 times
// 5th bulb flipped 1 time
// 6th bulb flipped 4 times
// 7th bulb flipped 2 times
// 8th bulb flipped 4 times
// 9th bulb flipped 3 times
// 10th bulb flipped 4 times
// 11th bulb flipped 2 times
// 12th bulb flipped 6 times
// 13th bulb flipped 2 times
// 14th bulb flipped 4 times
// 15th bulb flipped 4 times
// 16th bulb flipped 5 times
// ...
// It's easy to understand that if bulbs flipped odd times, the bulbs are on.
// By contrast, the rest turned even times remained off.
// We observed that bulbs numbered as 1, 4, 9, 16,...,x^2 which are all
// perfect squares, are always flipped odd times.
// Explanation as follows,
// For bulb numbered x=i*j, both ith round and jth round the bulb will be flipped,
// which means the flipped times on this bulb is aways even except i=j.
// In the case that i=j which means x is a perfect square, we can easily draw the conclusion
// that the bulb flipped odd times
// Above facts explains the observation we have at the beginning of the function.
return (int) Math.sqrt(n);
}
}