Integer Square Root

Lab C Intermediate 20 points

For each number print its integer square root (largest r with r² ≤ n) using binary search, without math.h.

Input

n, then n non-negative integers.

Output

n lines.

Example

Input

Output

Sample input available Sample output available

Editor

Hints

Binary search on the answer.

Compare as double to avoid overflow of mid * mid.

Solution explanation

Binary search works on any monotonic question, not just arrays.

Show solution

#include <stdio.h>

int isqrt(int n) {
    int lo = 0, hi = 46341, ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if ((double) mid * mid <= n) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}

int main() {
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &x);
        printf("%d\n", isqrt(x));
    }
    return 0;
}

Output

Answer