Challenge: Integer Square Root

Lab C++ Intermediate 20 points

Read n and print the largest whole number r with r × r ≤ n, using binary search on the answer (no sqrt).

Input

One whole number n (0 ≤ n ≤ 10¹⁸).

Output

One number.

Example

Input

Output

Sample input available Sample output available

Editor

C++

Hints

The answer is between 0 and 10⁹.

Check mid <= n / mid instead of mid * mid <= n to avoid overflow.

Solution explanation

About 30 steps for any n up to 10¹⁸.

Show solution

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    long long lo = 0, hi = 1000000000LL;
    while (lo < hi) {
        long long mid = lo + (hi - lo + 1) / 2;
        if (mid <= n / mid) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << endl;
    return 0;
}

Output

Answer