Square Root Of An Integer

Easy
0/40
Average time to solve is 20m
profile
Contributed by
45 upvotes
Asked in companies
OraclePharmEasyShareChat

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1
2
8
9
Sample Output 1
2
3
Explanation Of Input 1
The greatest non-negative integer for test case 1 whose square is less than equal to 8 is 2 as the square of 3 is 9 which is greater than 8.

The greatest non-negative integer for test case 2 whose square is less than equal to 9 is 3 as the square of 4 is 16 which is greater than 9.
Sample Input 2
2
1
0
Sample Output 2
1
0
Constraints
1 <= T <= 10^4
0 <= A <= 10^5

Time Limit: 1 sec
Expected Time Complexity:
Time Complexity : O(log(n))
Space Complexity : O(1)
Hint

Can we use linear search to solve this problem?

Approaches (2)
Using Linear Search

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.
Time Complexity

O(A), where A is given in each test case.

 

As all integers from 0 to A will be visited exactly once, the time complexity will O(A).

Space Complexity

O(1)

 

Constant space is used.

Code Solution
(100% EXP penalty)
Square Root Of An Integer
Full screen
Console