0
$\begingroup$

Recently I was working on a LeetCode question

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only 
the integer part of the result is returned.

Example 1:

Input: 4
Output: 2
Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.

Here is a solution that I really like and understand, except for one line. It is using binary search to get to the solution:

int mySqrt(int x) {
    if (x == 0) return x;
    int left = 1, right = INT_MAX, mid;
    while(left < right) {
        mid = left + (right - left)/2;
        if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
            return mid; 
        }
        if (mid < x/mid) {
            left = mid + 1;
        } else { // mid > x/mid
            right = mid;
        }
    }
    return right;
}

The conceptual question is: why is it true that given a particular number, say $i$, $$(i^2 \leq x) \land ((i + 1)^2 > x)$$ returns whether or not $i$ is the truncated integer representation of the square root of $x$? (The code block above returns on the identical condition, but inequality is rearranged to avoid integer overflow)

$\endgroup$
1
  • $\begingroup$ Why don't you try an example? Try $x=\sqrt{2}$ or $x=\sqrt{3}$ or $x=\sqrt{5}$ and see which values of $i$ make the condition hold, and see if you spot a pattern and can deduce why it is happening..... $\endgroup$
    – D.W.
    Commented Mar 6, 2020 at 6:07

1 Answer 1

1
$\begingroup$

I'll put the two inequalities together, for readability: $i^2 \leq x < (i+1)^2$.

Taking the positive square of a positive number is a monotone function. Hence, $$i^2 \leq x < (i+1)^2 \implies i \leq |\sqrt{x}| < i +1$$

Then, the interger part of $|\sqrt{x}|$ is obviously $i$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.