LeetCode - Algorithms - 69. Sqrt(x)

Java

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int mySqrt(int x) {
		if (x < 0)
			return 0;
		else if (x < 2)
			return x;
		else {
			long smallCandidate = mySqrt(x >> 2) << 1;
			long largeCandidate = smallCandidate + 1;
			if (largeCandidate*largeCandidate > x)
				return new Long(smallCandidate).intValue();
			else
				return new Long(largeCandidate).intValue();
		}       
    }
}

Submission Detail

  • 1017 / 1017 test cases passed.
  • Runtime: 36 ms
  • Your runtime beats 17.73 % of java submissions.

2

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int mySqrt(int x) {
		if (x==0 || x==1) return x;
		long i=1, result=1;
		while(result<=x) {
			i++;
			result = i*i;
		}
		return new Long(i-1).intValue();       
    }
}

Submission Detail

  • 1017 / 1017 test cases passed.
  • Runtime: 33 ms
  • Your runtime beats 24.03 % of java submissions.

3 O(logn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int mySqrt(int x) {
		if (x == 0 || x == 1)
			return x;

		long start = 1, end = x, ans = 0;
		while (start <= end) {
			long mid = (start + end) / 2;

			if (mid * mid == x)
				return new Long(mid).intValue();

			if (mid * mid < x) {
				start = mid + 1;
				ans = mid;
			} else
				end = mid - 1;
		}
		return new Long(ans).intValue();       
    }
}

Submission Detail

  • 1017 / 1017 test cases passed.
  • Runtime: 16 ms
  • Your runtime beats 95.09 % of java submissions.

ref