0% completed
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
Z. E.2 years ago
Same here. Was a bit confused why they provided the binary search solution.
Paul B.2 years ago
Consider the time complexity of your solution compared to binary search.
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.
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 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...
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
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 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