top of page

Looking to master object-oriented and system design for tech interviews or career growth?

  • Improve your system design and machine coding skills.

  • Study with our helpful resources.

  • Prepare for technical interviews and advance your career.

**We're in beta mode and would love to hear your feedback.

Square Root of Integer InterviewBit Solution

Sep 6, 2020
1 min read

Updated: Sep 14, 2020


Problem Description:

Given an integer, A. Compute and return the square root of A.

If A is not a perfect square, return floor(sqrt(A)).


DO NOT USE SQRT FUNCTION FROM STANDARD LIBRARY.


Input Format

The first and only argument given is integer A. 

Output Format

Return floor(sqrt(A)) 

Constraints

1 <= A <= 10^9 

For Example

Input 1:
    A = 11
Output 1:
    3
Input 2:
    A = 9
Output 2:
    3


Approach


To find sqrt of a number, we can do binary search on range, 0 to the given number. If for any mid-value, it's square increases more than the given number we will shift towards the lower number, otherwise the higher number.



Time & Space Complexity:

Time Complexity: O(logN)
Space Complexity: O(1)


Solution:


Code in C++



1 Comment


GavinOwens
1 day ago

https://sportwettenohneoasis.info caught my attention while reading, and the binary search on the range 0 to A makes sense for keeping the time down to O(logN). The overflow risk when squaring mid is the part that always trips people up in interviews, so it's worth mentioning that casting to long long before the multiplication is basically mandatory at these constraints. I've seen solutions pass locally and fail on the platform just because of that one detail.

Like
bottom of page