Square Root of an Integer Challenge

Given an integer 'A', the objective is to find the largest non-negative integer whose square is less than or equal to 'A'.

The square of a number is defined as the product of the number with itself. For example, the square of 3 is 9.

Example:

Input:

T = 2
A = 10
A = 15

Output:

3
3

Explanation:

For A = 10, 3² = 9 which is ≤ 10, but 4² = 16 which is 10. Hence, the output is 3. Similarly, for A = 15, the greatest integer whose square is ≤ 15 is 3.

Constraints:

1 ≤ T ≤ 10⁴

0 ≤ A ≤ 10⁵

Time Limit: 1 sec

Note:

You do not need to print anything; the necessary functionality to print has already been accounted for. Just carry out the function implementation.

Additional Task:

Consider whether it is possible to compute the square root in O(log(n)) time complexity.

Question

Square Root of an Integer Challenge

Given an integer 'A', the objective is to find the largest non-negative integer whose square is less than or equal to 'A'.

The square of a number is defined as the product of the number with itself. For example, the square of 3 is 9.

Example:

Input:

T = 2
A = 10
A = 15

Output:

3
3

Explanation:

For A = 10, 3² = 9 which is ≤ 10, but 4² = 16 which is > 10. Hence, the output is 3. Similarly, for A = 15, the greatest integer whose square is ≤ 15 is 3.

Constraints:

1 ≤ T ≤ 10⁴
0 ≤ A ≤ 10⁵
Time Limit: 1 sec

Note:

You do not need to print anything; the necessary functionality to print has already been accounted for. Just carry out the function implementation.

Additional Task:

Consider whether it is possible to compute the square root in O(log(n)) time complexity.

Accepted Answer

Find the largest non-negative integer whose square is less than or equal to a given integer.

Use binary search to efficiently find the square root of the given integer.
Start with a range from 0 to the given integer and iteratively narrow down the range based on the square of the middle value.
Return the largest integer whose square is less than or equal to the given integer.