A square number is 1+3+5+7+..., JAVA code


  • 121
    F
    public boolean isPerfectSquare(int num) {
         int i = 1;
         while (num > 0) {
             num -= i;
             i += 2;
         }
         return num == 0;
     }
    

    The time complexity is O(sqrt(n)), a more efficient one using binary search whose time complexity is O(log(n)):

    public boolean isPerfectSquare(int num) {
            int low = 1, high = num;
            while (low <= high) {
                long mid = (low + high) >>> 1;
                if (mid * mid == num) {
                    return true;
                } else if (mid * mid < num) {
                    low = (int) mid + 1;
                } else {
                    high = (int) mid - 1;
                }
            }
            return false;
        }
    

    One thing to note is that we have to use long for mid to avoid mid*mid from overflow. Also, you can use long type for low and high to avoid type casting for mid from long to int.
    And a third way is to use Newton Method to calculate the square root or num, refer to Newton Method for details.

    public boolean isPerfectSquare(int num) {
            long x = num;
            while (x * x > num) {
                x = (x + num / x) >> 1;
            }
            return x * x == num;
        }
    

  • 0
    H
    This post is deleted!

  • 3
    W

    Let x be the number of iterations needed to solve the problem,
    and let Σ be the sum from i = 1 to x.
    Σ(1 + 2i) = n =>
    x + 2Σi = n =>
    x + 2(x(x+1)) = n =>
    2x^2 + 3x = n =>
    x = [-3 +/- sqrt(9 + 8n)]/4 =>
    you can see that n is in a square root term, so the complexity should be O(sqrt(n)).


  • 39
    S

    This is a math problem:
    1 = 1
    4 = 1 + 3
    9 = 1 + 3 + 5
    16 = 1 + 3 + 5 + 7
    25 = 1 + 3 + 5 + 7 + 9
    36 = 1 + 3 + 5 + 7 + 9 + 11
    ....
    so 1+3+...+(2n-1) = (2n-1 + 1)n/2 = nn


  • 0
    C

    complexity is sqrt n. Far slow than O(1) provided by dploop and log(n) from StefanPochmann


  • 2
    S

    Can someone explain me why I had a similar version, but just do addition, however, I got TLE:

    public boolean isPerfectSquare(int num) {
        int i = 1, temp = 1;
        while(temp < num){
            i += 2;
            temp += i;
        }
        return temp == num;
    }
    

  • 3
    F

    If num is Integer.MAX_VALUE, you will got overflow.


  • 0
    H

    change the temp to a long, and you make it corrent


  • 0
    S

    Awesome! You guys rock!


  • 0
    Z
    This post is deleted!

  • 0
    F
    This post is deleted!

  • 0
    N

  • 2
    L

    @shuimulinxi said in A square number is 1+3+5+7+..., JAVA code:

    This is a math problem:
    1 = 1
    4 = 1 + 3
    9 = 1 + 3 + 5
    16 = 1 + 3 + 5 + 7
    25 = 1 + 3 + 5 + 7 + 9
    36 = 1 + 3 + 5 + 7 + 9 + 11
    ....
    so 1+3+...+(2n-1) = (2n-1 + 1)n/2 = nn

    :clap:


  • 0
    D

    @fhqplzj Very good solution. BTW, why is your reputation a negative number?


  • 0
    I

    @fhqplzj Nice idea, but it is n^0.5, worse than binary search logn.


  • 0
    R

    @iambright Hi iambright, could you explain more of why this is n^0.5? I thought it is O(n) cuz it need n/2 times check. Let me know if I'm wrong.


  • 1
    I

    @River3 1, 4, 9, 16, ... num = 1^2, 2^2, 3^2, 4^2, ..., num^0.5^2.


  • 0
    H

    great method,awesome


  • 0
    D

    actually O(log(n)) is more efficient then O(sqrt(n)) (it's obvious that n^2 is better than 2^n, the curve of sqrt(n) and log(n) is the opposite)


  • 4

    Here is an alternative binary search solution for your reference. The invariant is sqrt(x) must be included in [l, r] and it holds:

    1. Initialize: for any num >= 1, sqrt(num) must be in [1,num], so we add a check in the beginning.
    2. Maintain: If num/m - m >= 0, we cannot ensure sqrt(x) is outside, eg 3*3<10. Otherwise, it's safe to shrink from right side. But if l == r-1, we set l=m which incurs dead loop. Therefore we ceiling m rather than floor.
    3. Terminate: since we make progress in every case of the loop body even if l == r-1, the loop definitely terminates.

    At last, we have l==r after the loop which means the square of l is closest to num. So we can know if num is valid perfect square by checking l*l == num.

        public boolean isPerfectSquare(int num) {
            if (num <= 0) return false;
            int l = 1, r = num;
            while (l < r) {
                int m = l + (r - l) / 2 + 1;
                if (num / m >= m) l = m;
                else r = m - 1;
            }
            return l * l == num;
        }
    

    ps: Note that the difference between 69-Sqrt and 367-Valid Perfect Square problem.


Log in to reply
 

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