int Solution::sqrt(int A) {
    if (A == 1) return 1;
    long long from = 1;
    long long to = A;
    long long res = 0;
    while(from <= to) {
        long long mid = from + (to - from) / 2;
        if (mid * mid == A) return mid;
        if (mid * mid < A) {res = mid; from = mid + 1;}
        else               to = mid - 1;
    }

    return res;
}