Share my o(1) solution with explanation


  • 179
    K
    class Solution {
    public:
        int bulbSwitch(int n) {
            return sqrt(n);
        }
    };
    

    As we know that there are n bulbs, let's name them as 1, 2, 3, 4, ..., n.

    1. You first turn on all the bulbs.
    2. Then, you turn off every second bulb.(2, 4, 6, ...)
    3. On the third round, you toggle every third bulb.(3, 6, 9, ...)
    4. For the ith round, you toggle every i bulb.(i, 2i, 3i, ...)
    5. For the nth round, you only toggle the last bulb.(n)

    If n > 6, you can find that bulb 6 is toggled in round 2 and 3.

    Later, it will also be toggled in round 6, and round 6 will be the last round when bulb 6 is toggled.

    Here, 2,3 and 6 are all factors of 6 (except 1).


    Prove:

    We can come to the conclusion that the bulb i is toggled k times.

    Here, k is the number of i's factors (except 1).

    k + 1 will be the total number of i's factors


    For example:

    • Factors of 6: 1, 2, 3, 6 (3 factors except 1, so it will be toggled 3 times)
    • Factors of 7: 1, 7 (1 factors except 1, so it will be toggled once)
      ....

    Now, the key problem here is to judge whether k is even or odd.


    Since all bulbs are on at the beginning, we can get:

    • If k is odd, the bulb will be off in the end.(after odd times of toggling).
    • If k is even, the bulb i will be on in the end (after even times of toggling).

    As we all know, a natural number can divided by 1 and itself, and all factors appear in pairs.

    When we know that p is i's factor, we are sure q = i/p is also i's factor.

    If i has no factor p that makes p = i/p, k+ 1 is even.

    If i has a factor p that makes p = i/p (i = p^2, i is a perfect square of p), k+ 1 is odd.


    So we get that in the end:

    • If i is a perfect square , k+ 1 is odd, k is even (bulb i is on).
    • If i is NOT a perfect square , k+ 1 is even, k is odd (bulb i is off).

    We want to find how many bulbs are on after n rounds (In the end).

    That means we need to find out how many perfect square numbers are NO MORE than n.

    The number of perfect square numbers which are no more than n, is the square root of the maximum perfect square number which is NO MORE than n


    Result:

    The square root of the maximum perfect square number which is NO MORE than n is the
    integer part of sqrt(n).

    (If i = 1, it will NEVER be toggled, k is 0 (even) here which meets the requirement.)


  • 0
    X
    This post is deleted!

  • 0
    X

    very cool ! how you can think about like that way ?


  • 0
    W

    Feel I might have seen this as a homework problem when I took discrete math, classic counting problem.

    However, sqrt(n) is probably not O(1).


  • 0
    A

    What a beautiful solution, thanks for sharing!


  • 0
    M

    It is O(log(n)).


  • 0

    Just print the indexes of ON bulb for a random N, then everyone should notice this rule easily.


  • 0
    Z

    Great solution with clear explanation. Like it!


  • 0
    V

    Respect ,although i have no patience/mood to read the provement ;-)


  • 1
    C

    all factors appear in pairs!!!!
    what a wonderful explanation! thanks for sharing


  • 0
    D

    You can solve it like this
    For any number N, equals to I * J, for example, 8 = 1* 8, = 2*4
    For this question, if(I != J), then the bulb will be off, if I == J, then it is the square of N, and it will be on


  • 0
    R

    great solution. However I get confused of the argument:
    "If i has no factor p that makes p = i/p, k+ 1 is even."
    "If i has a factor p that makes p = i/p (i = p^2, i is a perfect square of p), k+ 1 is odd."
    The second one is absolutely right, but I'm not sure with the first one.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.