Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. If m² ≤ n then every smaller number also works — binary search for the largest such m.
  2. 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);
    }
}

Solve Square Root (Floor) online · All practice problems