Scale Engineer

Sqrt(x)

Easy
#0069Time: O(sqrt(x))Space: O(1)17 companies
Patterns
Math
Algorithms
Binary Search
Companies
AccentureAdobeAmazonApple

Prompt

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

  • For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

 

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

 

Constraints:

  • 0 <= x <= 231 - 1

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves iterating through numbers starting from 1 and checking if their square is equal to or just exceeds the input x. The integer square root is the largest integer i for which i*i <= x.

Algorithm

  • Handle the edge case where x is 0. If x is 0, the square root is 0.
  • Initialize a loop counter i to 1. Use a long for i to prevent overflow during multiplication.
  • In each iteration, check if i * i > x.
  • If this condition is met, it means (i-1)*(i-1) <= x and i*i > x. Therefore, i-1 is the answer. Return (int)(i-1).
  • If i * i == x, then i is the perfect square root, return (int)i.
  • The loop will eventually terminate because for a large enough i, i*i will exceed x.

Walkthrough

We can iterate with a variable i from 1 upwards. For each i, we compute its square. To avoid integer overflow when calculating i*i for large i, it's crucial to use a larger data type, like long in Java. The loop continues as long as i*i <= x. When the loop finds an i such that i*i > x, the previous integer, i-1, must be the integer square root of x.

class Solution {    public int mySqrt(int x) {        if (x == 0) {            return 0;        }        for (long i = 1; i <= x; i++) {            if (i * i > x) {                return (int) (i - 1);            }            if (i * i == x) {                return (int) i;            }        }        return -1; // Should not be reached for non-negative x    }}

Complexity

Time

O(sqrt(x))

Space

O(1)

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Inefficient for large values of x. It can lead to a "Time Limit Exceeded" error on online judges.

Solutions

public class Solution { public int MySqrt ( int x ) { int l = 0 , r = x ; while ( l < r ) { int mid = ( l + r + 1 ) >>> 1 ; if ( mid > x / mid ) { r = mid - 1 ; } else { l = mid ; } } return l ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem