Can anyone help to explain why sqrt(n) equals to the count of square numbers below n?


  • 0
    Q

    I can understand the solution is to find the count of numbers below n which can be sqrt, but why sqrt(n) is right?


  • 0
    E

    n = 1,2,3 result = 1

    n = 4,5,6,7,8,9 result = 2

    n = 10,11.....14,15 result = 3

    n = 16,17.....23,24 result = 4

    rule: x² ≤n≤(x*(x+2)) x is result


  • -2
    A

    Reminder: Any bulb that toggles even times would turn out to be status ON. Otherwise, status OFF.

    For any non-perfect square number, say 8,
    the factors of 8 are 1,8,2,4. So that the 8th bulb would toggle at the 1st round, the 2nd round, the 4th round, and the 8th round. But we know that the 1st round is initial round, which all bulbs would be set to status ON. Therefore, the 8th bulb would toggle just three times or odd times. So that it would turn out to be status OFF.

    For any perfect square number, say 16,
    the factors of 16 are 1,16,2,8,4. The same idea as shown above, it would toggle four times or you can say even times. So that it would turn out to be status ON.

    In summary, we only need to count the number of perfect square number that is less than or equal to n.


  • 0
    P

    Hope it's not too late.

    If you want to count the number of Perfect Square Number(PSN) under 100.
    They are
    1x1 = 1
    2x2 = 4
    3x3 = 9
    4x4 = 16
    5x5 = 25
    6x6 = 36
    7x7 = 49
    8x8 = 64
    9x9 = 81
    10x10 = 100
    You've found something? The root of them are 1 to 10.
    Why? Because that's how we build PSN. By multiply a integer with it self.

    These are some example:
    n = 999? Root of 999 is 31.6. Then all PSN we got under 999 can be generated by 1 to 31. How many? 31.
    n = 321? Root of 999 is 17.9. Then all PSN we got under 321 can be generated by 1 to 17. How many? 17.

    Please vote me if this answer is useful so more people can see it.


  • 0

  • 0
    Q

    @LHearen thank you :)


  • 0
    Q

    @park9349 thank you :)


  • 0
    Q

    @ender_zz thank you :)


  • 0
    Q

    @Alahaga thank you :)


Log in to reply
 

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