319. Bulb Switcher #
Problem #
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 ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.
Return the number of bulbs that are on after n rounds.
Example 1:
Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off].
So you should return 1 because there is only one bulb is on.
Example 2:
Input: n = 0
Output: 0
Example 3:
Input: n = 1
Output: 1
Problem Summary #
Initially, there are n bulbs that are off. In the first round, you will turn on all the bulbs. In the following second round, you will turn off every second bulb.
In the third round, you toggle the switch of every third bulb (that is, turn on to off, and off to on). In the ith round, you toggle the switch of every i bulb. Until the nth round, you only need to toggle the switch of the last bulb.
Find and return how many bulbs are on after n rounds.
Solution Approach #
- Count the numbers from 1 to n that have an odd number of divisors
- A number x from 1 to n has an odd number of divisors, which means x is a perfect square
- Count the number of perfect squares from 1 to n: sqrt(n)
Code #
package leetcode
import "math"
func bulbSwitch(n int) int {
return int(math.Sqrt(float64(n)))
}
中文