Last Updated: 12 Jan, 2021

Square Root Of An Integer

Easy

Asked in companies

Solve now

Problem statement

You are given an integer ‘A’. Your task is to find the greatest non-negative integer whose square is less than or equal to ‘A’.

Square of a number is the product of the number with itself. For e.g. square of 3 is 9.

Input Format

The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.

The first line of each test case contains a single integer ‘A’.

Output Format

For each test case, print the greatest positive integer whose square is less than or equal to ‘A’.

Print the output of each test case in a separated line.

Note

You do not need to print anything; it has already been taken care of. Just implement the given function.

Solve now

Approaches

01 Approach

We will iterate over all possible integers from 0 to ‘A’ and return the greatest possible integer whose square is less than or equal to ‘A’.

Algorithm

Initialize a variable ‘ans’ to store the result.
Iterate from 0 to ‘A’ using a variable ‘i’.
- If i*i ≤ A, Update ans with i*i.
Return ans.

Solve now

02 Approach

Let our final answer be ‘x’. For all numbers (r <= x), r * r will be less than or equal to ‘A’ and for all numbers (r > x), r * r will be greater than ‘A’. Hence, we can binary search for this number ‘x’.

Algorithm

We will initialize ‘start’ to 0 and end to ‘A’. Then ‘mid’ will be equal to (‘start’+‘end’) / 2.
While ‘start’ <= ‘end’:
- If mid * mid <= A , we set ‘start’ to mid + 1;
- Else, we set ‘end’ to mid - 1.
We finally return ‘start’ - 1 as our answer.

Solve now