Java Three Solutions 1,3,5,.. Sequence/Binary Search/Newton


  • 23
    1. a square number is 1+3+5+7+... Time Complexity O(sqrt(N)) (Credit to lizhibupt, thanks for correcting this).
    2. binary search. Time Complexity O(logN)
    3. Newton Method. See [this wiki page][1]. Time Complexity is close to constant, given a positive integer.
    
    
        public boolean isPerfectSquare(int num) {
          if (num < 1) return false;
          for (int i = 1; num > 0; i += 2)
            num -= i;
          return num == 0;
        }
        
        public boolean isPerfectSquare(int num) {
          if (num < 1) return false;
          long left = 1, right = num;// long type to avoid 2147483647 case
        
          while (left <= right) {
            long mid = left + (right - left) / 2;
            long t = mid * mid;
            if (t > num) {
              right = mid - 1;
            } else if (t < num) {
              left = mid + 1;
            } else {
              return true;
            }
          }
        
          return false;
        }
        
        boolean isPerfectSquare(int num) {
          if (num < 1) return false;
          long t = num / 2;
          while (t * t > num) {
            t = (t + num / t) / 2;
          }
          return t * t == num;
        }
    
    
    
      [1]: https://en.wikipedia.org/wiki/Newton%27s_method

  • 6
    L

    The time complexity of solution 1 should be O(sort(n)), not linear:

    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)).


  • 0

    You are right, the complexity of solution 1 should be O(sqrt(n))


  • 0
    A

    Newton's method will fail if the input is 1.


  • 4
    A

    Your implementation of Newton's method will fail if the input is 1 because you divide the number by 2 initially.

    Modified implementation which will work with all test cases:

    public boolean isPerfectSquare_newton(int num) { // O(1)
        // Newtons's method.
        // Find square root of num and square it
        // square == num ? true : false;
    
        long t = num;
        while (t * t > num) {
            t = (t + num / t) / 2;
        }
        return t * t == num;
    }

  • 0
    K

    num can be 0


  • 0
    F

    You are so clever.


  • 0
    J

    @kira4 Nop. The question states: "Given a positive integer num".


Log in to reply
 

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