// Arup Guha
// 4/29/2022
// Solution to Spring 2022 COP 3502 Final Exam Question 7

#include <stdio.h>

long long intSquareRoot(long long number);

int main(void) {

    // Some tests...
    printf("%lld\n", intSquareRoot(10000000000000ll));
    printf("%lld\n", intSquareRoot(0ll));
    printf("%lld\n", intSquareRoot(196ll));
    printf("%lld\n", intSquareRoot(224ll));
    printf("%lld\n", intSquareRoot(999999999999999999ll));
    printf("%lld\n", intSquareRoot(1000000000000000000ll));

    return 0;
}

// Returns the maximum integer x such that x*x <= number.
long long intSquareRoot(long long number) {

    // Safe bounds according to the prompt.
    long long low = 0, high = 1000000000ll;

    // Usual integer binary search loop.
    while (low < high) {

        // It turns out we want this mid pt.
        long long mid = (low+high+1)/2;

        // Too big, so the highest our answer could be is mid-1.
        if (mid*mid > number)
            high = mid-1;

        // This is small enough, so our answer is at least mid.
        else
            low = mid;
    }

    // Ta da!
    return low;
}