LeetCode 69 - Sqrt(x)


https://leetcode.com/problems/sqrtx/discuss/25270/What-is-the-complexity-of-babylonian-method
IMHO, it's hard to determine the big O complexity defined in algorithm world. The time complexity determined by 1. the accuracy (e in your solution) and 2. how far n is away from 0 (The far the quicker)

X.
这道题要求我们求平方根，我们能想到的方法就是算一个候选值的平方，然后和x比较大小，为了缩短查找时间，我们采用二分搜索法来找平方根，这里属于博主之前总结的LeetCode Binary Search Summary 二分搜索法小结中的第三类的变形，找最后一个不大于目标值的数
    int mySqrt(int x) {
        if (x <= 1) return x;
        int left = 0, right = x;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (x / mid >= mid) left = mid + 1;
            else right = mid;
        }
        return right - 1;
    }


    public int mySqrt(int x) {
        long l=0,r=x; //in case of overflow
        while(l<r){
            long mid=l+(r-l)/2+1;
            if(mid*mid>x) r=mid-1;
            else l=mid;
        }
        return (int)l;
    }

https://www.cnblogs.com/grandyang/p/4346413.html
这道题还有另一种解法，是利用牛顿迭代法，记得高数中好像讲到过这个方法，是用逼近法求方程根的神器，在这里也可以借用一下，可参见网友Annie Kim's Blog的博客，因为要求x2 = n的解，令f(x)=x2-n，相当于求解f(x)=0的解，可以求出递推式如下：
xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2

    int mySqrt(int x) {
        if (x == 0) return 0;
        double res = 1, pre = 0;
        while (abs(res - pre) > 1e-6) {
            pre = res;
            res = (res + x / res) / 2;
        }
        return int(res);
    }


    int mySqrt(int x) {
        long res = x;
        while (res * res > x) {
            res = (res + x / res) / 2;
        }
        return res;
    }

X. O(32N) - different but not most efficient
https://leetcode.com/problems/sqrtx/discuss/25048/Share-my-O(log-n)-Solution-using-bit-manipulation
Since sqrt(x) is composed of binary bits, I calculate sqrt(x) by deciding every bit from the most significant to least significant. Since an integer n can have O(log n) bits with each bit decided within constant time, this algorithm has time limit O(log n), actually, because an Integer can have at most 32 bits, I can also say this algorithm takes O(32)=O(1) time.
 public int sqrt(int x) {
    if(x==0)
        return 0;
    int h=0;
    while((long)(1<<h)*(long)(1<<h)<=x) // firstly, find the most significant bit
        h++;
    h--;
    int b=h-1;
    int res=(1<<h);
    while(b>=0){  // find the remaining bits
        if((long)(res | (1<<b))*(long)(res |(1<<b))<=x)
            res|=(1<<b);
        b--;
    }
    return res;
}

http://www.ardendertat.com/2012/01/26/programming-interview-questions-27-squareroot-of-a-number/
Implement int sqrt(int x). Compute and return the square root of x.
we can make this search process faster by dividing the range into two halves and deciding whether the square root is found and which half to explore according to the center value of the range. The idea of this accelerated process is similar to binary search of a target value in a sorted array. Note that when coding the above process, do avoid integer overflowing.
X. O(N) - linear search
def sqrt1(num):
    if num<0:
        raise ValueError
    if num==1:
        return 1
    for k in range(1+(num/2)):
        if k**2==num:
            return k
        elif k**2>num:
            return k-1
    return k
The complexity of this approach is O(N), because we have to check N/2 numbers in the worst case. This linear algorithm is pretty inefficient, we can use some sort of binary search to speed it up.

X. Binary Search, BisectionWe know that the result is between 0 and N/2, so we can first try N/4 to see whether its square is less than, greater than, or equal to N. If it’s equal then we simply return that value. If it’s less, then we continue our search between N/4 and N/2. Otherwise if it’s greater, then we search between 0 and N/4. In both cases we reduce the potential range by half and continue, this is the logic of binary search. 
def sqrt2(num):
    if num<0:
        raise ValueError
    if num==1:
        return 1
    low=0
    high=1+(num/2)
    while low+1<high:
        mid=low+(high-low)/2
        square=mid**2
        if square==num:
            return mid
        elif square<num:
            low=mid
        else:
            high=mid
    return low
One difference from regular binary search is the condition of the while loop, it’s low+1<high instead of low<high. Also we have low=mid instead of low=mid+1, and high=mid instead of high=mid-1.

public int sqrt(int x) {
        if (x < 0)
            return -1;
        if (x == 0)
            return 0;
        int lower = 1, upper = x/2+1;   // Lower and upper bound of sqrt(x)
        while (lower <= upper) {
            int center = (lower+upper) / 2;
            if (center <= x/center && center+1 > x/(center+1))  // Use this form to avoid overflow
                return center;
            if (center < x/center)  // sqrt(x) is in the right half
                lower = center + 1;
            else        // sqrt(x) is in the left half
                upper = center - 1;
        }
        // Dummy return
        return 0;
    }
https://leetcode.com/problems/sqrtx/discuss/25047/A-Binary-Search-Solution
public int sqrt(int x) {
    if (x == 0)
        return 0;
    int left = 1, right = Integer.MAX_VALUE;
    while (true) {
        int mid = left + (right - left)/2;
        if (mid > x/mid) {
            right = mid - 1;
        } else {
            if (mid + 1 > x/(mid + 1))
                return mid;
            left = mid + 1;
        }
    }
}

http://blog.csdn.net/at8008/article/details/17238745
double sqrt(double x){
    if(x<0) return -1;
    else if (x>0 && x<1)
 return 1.0/sqrt(1, 1/x, 1/x);
    else
 return sqrt(1, x, x);
}

doubble sqrt(double start, double end, double x){
    double mid = start + (end-start)/2;
    // product = mid*mid; -- this will overflow!
    double div = x/mid;
    if(Math.abs(div-mid) < Math.pow(0.1,10))
 return mid;
    else if (div < x)
 return sqrt(start, mid, x);
    else
 return sqrt(mid, end, x);
}
http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html
二分搜索
对于一个非负数n，它的平方根不会小于大于（n/2+1）（谢谢@linzhi-cs提醒）。在[0, n/2+1]这个范围内可以进行二分搜索，求出n的平方根。
注：在中间过程计算平方的时候可能出现溢出，所以用long long。
int sqrt(int x) {
 2     long long i = 0;
 3     long long j = x / 2 + 1; // key +1;
 4     while (i <= j)
 5     {
 6         long long mid = (i + j) / 2;
 7         long long sq = mid * mid;
 8         if (sq == x) return mid;
 9         else if (sq < x) i = mid + 1;
10         else j = mid - 1;
11     }
12     return j;
13 }
  1. public int sqrt(int x) { 
  2.         double error = 0.0000001f;  
  3.         double high = x;  
  4.         double low = 0;  
  5.         while(high-low> error){  
  6.             double mid = (high+low)/2;  
  7.             if(mid*mid>x){  
  8.                 high = mid;  
  9.             }else {  
  10.                 low = mid;  
  11.             }  
  12.         }  
  13.         return (int)Math.floor(high);  
  14.     }  
http://www.lifeincode.net/programming/leetcode-sqrtx-java/
    public int sqrt(int x) {
        long i = 0;
        long j = x / 2 + 1;
        while (i <= j) {
            long mid = (i + j) / 2;
            if (mid * mid == x)
                return (int)mid;
            if (mid * mid < x)
                i = mid + 1;
            else
                j = mid - 1;
        }
        return (int)j;
    }

 According to Newton's Method(http://en.wikipedia.org/wiki/Newton's_method), we can use
x_(k+1)=1/2(x_k+n/(x_k))
to get the sqrt(x)  res = (res + x / res) / 2;
int sqrt(int x) {
        if (x==0) {return 0;}
        if (x==1) {return 1;}
       
        double x0 = 1;
        double x1;
        while (true){
            x1 = (x0+ x/x0)/2;
            if (abs(x1-x0)<1){return x1;}
            x0=x1;
        }
http://blog.csdn.net/doc_sgl/article/details/12404971

2. 牛顿迭代法


   为了方便理解，就先以本题为例：
   计算x2 = n的解，令f(x)=x2-n，相当于求解f(x)=0的解，如左图所示。
   首先取x0，如果x0不是解，做一个经过(x0,f(x0))这个点的切线，与x轴的交点为x1。
   同样的道理，如果x1不是解，做一个经过(x1,f(x1))这个点的切线，与x轴的交点为x2。
   以此类推。
   以这样的方式得到的xi会无限趋近于f(x)=0的解。
   判断xi是否是f(x)=0的解有两种方法：
   一是直接计算f(xi)的值判断是否为0，二是判断前后两个解xi和xi-1是否无限接近。
经过(xi, f(xi))这个点的切线方程为f(x) = f(xi) + f’(xi)(x - xi)，其中f'(x)为f(x)的导数，本题中为2x。令切线方程等于0，即可求出xi+1=xi - f(xi) / f'(xi)。
继续化简，xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2。
有了迭代公式xi+1= (xi + n/xi) / 2，程序就好写了。关于牛顿迭代法，可以参考wikipedia以及百度百科。
  1. int sqrt(int x) {  
  2.         if (x ==0)  
  3.             return 0;  
  4.         double pre;  
  5.         double cur = 1;  
  6.         do  
  7.         {  
  8.             pre = cur;  
  9.             cur = x / (2 * pre) + pre / 2.0;  
  10.         } while (abs(cur - pre) > 0.00001);  
  11.         return int(cur);  
  12.     } 
http://www.geeksforgeeks.org/square-root-of-an-integer/
A Simple Solution to find floor of square root is to try all numbers starting from 1. For every tried number i, if i*i is smaller than x, then increment i. We stop when i*i becomes more than or equal to x.
O(√ n)
int floorSqrt(int x)
{
    // Base cases
    if (x == 0 || x == 1)
       return x;
    // Staring from 1, try all numbers until
    // i*i is greater than or equal to x.
    int i = 1, result = 1;
    while (result < x)
    {
       if (result == x)
          return result;
       i++;
       result = i*i;
    }
    return i-1;
}

https://reeestart.wordpress.com/2016/06/14/google-root-of-square/
Leetcode 原题，算n的平方根。原题n是integer, 面经是double。
对于integer的binary search要注意overflow, 对于double的binary search需要预设一个精度。
[Solution #2]
牛顿迭代法。把题目看做一个方程 y = x^2，而我们需要求的就是当y = n是x的解，也就是x^2 – n = 0的解。这个函数的导数为2x，所以在抛物线上任何一点的(x, y)的切线斜率就是2x, 所以
y / (x – x2) = 2x
x2就是比x更为近似的一个值，如果我们先猜一个x，那么x2就是我们的next guess，
代入得到
x2 = (x^2 + n) / 2x
于是我们随便猜一个x，无论它和正确答案差的有多离谱，通过上面方法不断近似，牛顿迭代法依然要比binary search快的多。
// double binary search
class Solution1 {
  double p = 0.0001;
  public double sqrt(double n) {
    if (n <= 0) {
      throw new IllegalArgumentException();
    }
    double l = 0;
    double r = n;
    double mid = (l + r) / 2.0;
    double prev = mid;
    do {
      if (mid * mid > n) {
        r = mid;
      }
      else {
        l = mid;
      }
      prev = mid;
      mid = (l + r) / 2.0;
    } while (Math.abs(prev - mid) > p);
    return mid;
  }
}
// int binary search, be careful of the Overflow
class Solution2 {
  public int sqrt(int n) {
    if (n < 0) {
      throw new IllegalArgumentException();
    }
    if (n <= 1) {
      return n;
    }
    int l = 1;
    int r = n / 2;
    while (l <= r) {
      int mid = (l + r) / 2;
      long square = (long) mid * mid;
      if (square == n) {
        return mid;
      }
      else if (square > n) {
        r = mid - 1;
      }
      else {
        l = mid + 1;
      }
    }
    return (long) l * l < n? l : l - 1;
  }
}
/*
  Newton's method double
  y = x^2 - n, find x that makes y = 0
  First guess: x = n
  Next guess: x = x - y/2x
*/
class Solution3 {
  double p = 0.001;
  public double sqrt(double n) {
    if (n < 0) {
      throw new IllegalArgumentException();
    }
    if (n == 0.0) {
      return n;
    }
    double x = n;
    double prev;
    do {
      prev = x;
      x = x - (x * x - n) / (2 * x);
    } while (Math.abs(x - prev) > p);
    return x;
  }
}
// Newton's method int
class Solution4 {
  public int sqrt(int n) {
    if (n < 0) {
      throw new IllegalArgumentException();
    }
    if (n <= 1) {
      return n;
    }
    long x = n;
    long prev = x;
    while (true) {
      prev = x;
      long square = x * x;
      long plusOne = (x + 1) * (x + 1);
      if (square == n) {
        break;
      }
      if (square < n && plusOne > n) {
        break;
      }
      x = x - (x * x - n) / (2 * x);
      if (prev == x) {
        break;
      }
    }
    return (long) x * x <= n? (int) x : (int) x - 1;
  }
}
X. https://leetcode.com/problems/sqrtx/discuss/25048/Share-my-O(log-n)-Solution-using-bit-manipulation
Since sqrt(x) is composed of binary bits, I calculate sqrt(x) by deciding every bit from the most significant to least significant. Since an integer n can have O(log n) bits with each bit decided within constant time, this algorithm has time limit O(log n), actually, because an Integer can have at most 32 bits, I can also say this algorithm takes O(32)=O(1) time.
 public int sqrt(int x) {
    if(x==0)
        return 0;
    int h=0;
    while((long)(1<<h)*(long)(1<<h)<=x) // firstly, find the most significant bit
        h++;
    h--;
    int b=h-1;
    int res=(1<<h);
    while(b>=0){  // find the remaining bits
        if((long)(res | (1<<b))*(long)(res |(1<<b))<=x)
            res|=(1<<b);
        b--;
    }
    return res;
}

Also check code at http://blog.csdn.net/linhuanmars/article/details/20089131
http://massivealgorithms.blogspot.com/2014/07/babylonian-method-for-square-root.html
Read full article from LeetCode - Sqrt(x) | Darren's Blog
at
Labels: , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts