Sqrt-D&C

import java.util.Scanner;

public class Main {
    public static int sqrt(int x, int l, int r) {
        int m = (l + r) / 2;
        if ((m + 1) * (m + 1) > x && m * m <= x) {
            return m;
        }
        if (m * m < x) {
            return sqrt(x, m, r);
        } else {
            return sqrt(x, l, m);
        }
    }

    public static void main(String[] args) {
        // Example usage
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(sqrt(n, 1, n));
    }
}