“This is the 15th day of my participation in the November Gwen Challenge. See details of the event: The Last Gwen Challenge 2021”.

Topic describes

This is 319 light bulb switch from LeetCode, medium difficulty.

Tag: math

We start with n bulbs turned off. In the first round, you will turn on all the light bulbs. Then in the second round, you will turn off one light bulb for every two.

In the third round, you switch on and off one bulb for every three.

In round I, you switch one light bulb for every I light bulbs. Until the NTH round, you only have to switch the last light bulb.

Find and return how many light bulbs are on after n rounds.

Example 1:

Input: n = 3 Output: 1 Explanation: Initially, the bulb state [off, off, off]. After the first round, the bulb state [on, on, on]. After the second round, the bulb state [on, off, on]. After the third round, the bulb state [on, off, off]. You should return 1 because only one bulb is still on.Copy the code

Example 2:

Input: n = 0 Output: 0Copy the code

Example 3:

Input: n = 1 Output: 1Copy the code

Tip:


  • 0 < = n < = 1 0 9 0 <= n <= 10^9

mathematics

This is a classic number theory problem.

Round III changes the state of all light bulbs numbered multiples of III (bulb numbering starting with 111).

One number is
x x The light bulb goes by
n n If the rear wheel is open, the condition is “the bulb has been switched several times.”

At the same time, a bulb can switch states a divisor number of times (deweighting).

Then the question is transformed into: how many numbers are there in [1,n][1,n][1,n], and the number of divisor is odd. These odd divisor bulbs are the last ones to light.

And according to the definition of “divisor”, we know that if a number KKK is a divisor of XXX, then Xk \frac{x}{k}kx is also a divisor of XXX, that is, “divisor” always appears in pairs, then the number of divisor of a number is odd, which means that a divisor appears 222 times in the decomposition process. K = XKK = \frac{x}{k}k=kx, that is, XXX is a perfect square (and vice versa).

The question ultimately translates to: How many perfect squares are there in [1,n][1,n][1,n]?

According to number theory, the number of perfect squares in [1,n][1,n][1,n] is ⌊n⌋\left \lfloor \ SQRT {n} \right \rfloor⌊n ⌋, That is, the last number of light bulbs is ⌊n⌋\left \lfloor \ SQRT {n} \right \rfloor⌊n ⌋.

Code:

class Solution {
    public int bulbSwitch(int n) {
        return (int)Math.sqrt(n); }}Copy the code
  • Time complexity: O(1)O(1)O(1)
  • Space complexity: O(1)O(1)O(1)

The last

This is the no.319 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks. We will first finish all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.