Integer Square Root

/*
 * Problem : Integer square root.
 * Input   : One integer n.
 * Output  : The root.
 * Approach: Binary search on the answer.
 * Time    : O(log n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long n) {
        // Step 1: The answer is between 0 and 10^8 (because n is at most 9 * 10^15).
        long low = 0;
        long high = 100_000_000L;

        // Step 2: Find the largest r with r * r <= n. The product fits in long, because r <= 10^8.
        while (low < high) {
            long mid = low + (high - low + 1) / 2;
            if (mid * mid <= n) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}