Grokking Data Structures & Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Simpler Solution

Roberto Pantoja

Jun 13, 2023

I came up with the following solution.

class Solution {
public:
  int mySqrt(int x) {
    int i = 0;

    while(i * i <= x){i++;}

    // TODO: Write your code here
    return i - 1;
  }
};

Basically, just increment i until you pass the square root, then return previous value.

Am I missing something? Why is the more complex solution the example?

6

1

Comments
Comments
Z
Z. E.2 years ago

Same here. Was a bit confused why they provided the binary search solution.

P
Paul B.2 years ago

Consider the time complexity of your solution compared to binary search.

Design Gurus
Design Gurus2 years ago

This solution is easy and readable but has higher time complexity. It has a time complexity of O(X/2) => O(X).

The binary search approach gives you O(logX) time complexity, which is considered better.

K
kurtanthony.w 2 years ago

There solution is better because it is done in O(logn) time while this is done in O(n).

Design Gurus
Design Gurus2 years ago

This algorithm fails for the input 2147395600 due to an integer overflow issue.

Integer Overflow: The maximum value an int can hold in Java is 2,147,483,647 (Integer.MAX_VALUE). When you have an input like 2147395600, the square of i becomes larger than Integer.MAX...

Kenny
Kenny2 years ago

consider growth asymptotically - how many numbers would I have to check for the sqrt of 10^100?

your function: runs 10^50 times before reaching the correct num

binary search: log2(10^100) = roughly 330 times

U
umesh 6 months ago

TC here is O(sqrt(X)) while with binary search it would be O(log(x)). For ex: x = 1M, this solution would take 1K iterations while binary search would take about 20.

Axel Castillo
Axel Castillo5 months ago

Imagine that your number is one hundrer thousan millon, you will iterate one by one each number untill find it.

With Binary Search you only look in a specific range of posibilities and is quicker, go to leetcode and loook for this problem, check the fastest and the slo...

On this page