Practice › Binary Search
Square Root (Floor)
Easy · Binary Search · Asked at Amazon, Microsoft, Apple, TCS, Infosys
Print ⌊√n⌋, the largest integer whose square is ≤ n, without using a built-in square root.
Input
One integer n.
Output
The floor of the square root.
Constraints
- 0 ≤ n ≤ 10^18
Binary search on the answer. Careful: mid * mid can overflow 64-bit — compare mid with n / mid instead.
Example 1
Input
8
Output
2
Example 2
Input
16
Output
4
Hints
- If m² ≤ n then every smaller number also works — binary search for the largest such m.
- m * m can overflow 64 bits near 10^18. Compare m ≤ n / m instead.
Approach
Search m in [1, n] for the largest value with m * m <= n. Written as m <= n / m, the check never overflows. Use the upper-mid lo + (hi − lo + 1) / 2 so the loop always moves when lo = mid. n = 0 is a special case (answer 0, and n / m with m = 0 would divide by zero). Python has math.isqrt, which is exact for big integers.
Complexity: O(log n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n;
cin >> n;
if (n < 2) {
cout << n << "\n";
return 0;
}
long long lo = 1, hi = min(n, 2000000000LL);
while (lo < hi) {
long long mid = lo + (hi - lo + 1) / 2;
if (mid <= n / mid) lo = mid;
else hi = mid - 1;
}
cout << lo << "\n";
return 0;
}Python solution
from math import isqrt
n = int(input())
print(isqrt(n))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
if (n < 2) {
System.out.println(n);
return;
}
long lo = 1, hi = Math.min(n, 2000000000L);
while (lo < hi) {
long mid = lo + (hi - lo + 1) / 2;
if (mid <= n / mid) lo = mid;
else hi = mid - 1;
}
System.out.println(lo);
}
}