Interview 150
Sqrt(x)
- Problem
- LC 69
- File
- interview150_LC69SqrtX.java
- Path
- pkg5leetcode/interview150/interview150_LC69SqrtX.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC69SqrtX.java
- Approach
- Binary search on answer in [0, x].
- Complexity
- Time O(log x), Space O(1)
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/*4 * Sqrt(x) | LC 695 * APPROACH: Binary search on answer in [0, x].6 * COMPLEXITY: Time O(log x), Space O(1)7 */8public class interview150_LC69SqrtX {9 static int mySqrt(int x) {10 if (x < 2) return x;11 int lo = 1, hi = x / 2;12 while (lo <= hi) {13 int mid = lo + (hi - lo) / 2;14 long sq = (long) mid * mid;15 if (sq == x) return mid;16 if (sq < x) lo = mid + 1;17 else hi = mid - 1;18 }19 return hi;20 }21 22 public static void main(String[] args) {23 check(mySqrt(4) == 2, "case1");24 check(mySqrt(8) == 2, "case2");25 System.out.println("all tests passed");26 }27 28 static void check(boolean cond, String name) {29 if (!cond) throw new AssertionError("FAILED: " + name);30 System.out.println(" PASS " + name);31 }32}