Sqrt(x) — Solution in Python, Java & C++
Sqrt(x) solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Microsoft.
Sqrt(x) is an easy coding problem on math and binary search, asked in Amazon, Microsoft and Infosys interviews.
- Difficulty: Easy
- Topics: Math, Binary Search
- Asked at: Amazon, Microsoft, Infosys
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return the square root of the non-negative integer x, rounded down to the nearest integer.
You may not use any built-in exponent or square-root function.
Example 1
Input: x = 4
Output: 2
Example 2
Input: x = 8
Output: 2
Explanation: The true root is about 2.828, which floors to 2.
Example 3
Input: x = 2147395600
Output: 46340
Explanation: The largest perfect square inside a 32-bit int.
Constraints
0 <= x <= 2147483647
Hints for Sqrt(x)
Hint 1
You are looking for the largest
rwithr · r <= x— a monotone predicate.Hint 2
Binary search
rover[1, 46341]; anything larger squares past a 32-bit integer.Hint 3
Compare with
mid · mid <= xin a type wide enough not to overflow, or bound the range instead.
How to solve Sqrt(x)
The predicate r · r <= x is true for a prefix of the candidate roots and false after, so binary search finds the boundary. Capping the range at 46341 keeps mid · mid inside a 32-bit integer.
Approach
- Return
xdirectly forx < 2. - Search
[1, 46341]for the largestmidwithmid · mid <= x, using the upper-biased midpoint(lo + hi + 1) / 2. - Return
lo.
Why it works
46340² = 2147395600 fits a signed 32-bit integer while 46341² = 2147488281 does not, so the search never evaluates an overflowing product. The upper-biased midpoint is what makes the 'largest satisfying value' loop terminate — with the usual (lo + hi) / 2 it would spin when hi == lo + 1.
Complexity
- Time —
O(log x) - Space —
O(1)
Pitfalls
mid · midoverflows a 32-bitintformidabove 46340 — either widen the type or cap the range as here.- Using the plain midpoint with
lo = midloops forever. - Floating-point
sqrtcan round the wrong way near a perfect square, and the problem forbids it anyway.
Reference solution
Python
def mySqrt(x: int) -> int:
if x < 2:
return x
lo, hi = 1, 46341
while lo < hi:
mid = (lo + hi + 1) // 2
if mid * mid <= x:
lo = mid
else:
hi = mid - 1
return loJava
public static int mySqrt(int x) {
if (x < 2) return x;
int lo = 1, hi = 46341;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if ((long) mid * mid <= x) lo = mid; else hi = mid - 1;
}
return lo;
}C++
int mySqrt(int x) {
if (x < 2) return x;
int lo = 1, hi = 46341;
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if ((long long) mid * mid <= x) lo = mid; else hi = mid - 1;
}
return lo;
}JavaScript
var mySqrt = function(x) {
if (x < 2) return x;
var lo = 1, hi = 46341;
while (lo < hi) {
var mid = (lo + hi + 1) >> 1;
if (mid * mid <= x) lo = mid; else hi = mid - 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 337 math problems · the whole catalogue
Learn the technique: Binary Search