Square root of an integer

Problem Statement

Given a non-negative integer x, compute and return the square root of x. Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Constraints:

• 0 <= x <= 2^31 - 1
• You are not allowed to use any built-in exponent function or operator

Example:

• Input: x = 8
• Output: 2
• Explanation: √8 = 2.828..., truncated to 2

Example 2:

• Input: x = 4
• Output: 2
• Explanation: √4 = 2 exactly

Example 3:

• Input: x = 0
• Output: 0

Approach 1: Brute Force (Linear Search)

Intuition

Start from 1 and keep checking if i*i <= x. The last i for which this holds is the answer.

Algorithm

1. Handle edge case: if x is 0 or 1, return x
2. Start from i = 1
3. While i * i <= x, increment i
4. Return i - 1

public class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        
        long i = 1;
        while (i * i <= x) {
            i++;
        }
        
        return (int)(i - 1);
    }
}

Complexity Analysis

• Time Complexity: O(√n) - We iterate up to √x times
• Space Complexity: O(1) - Constant space

Approach 2: Binary Search (Optimal)

Intuition

The answer lies between 0 and x. We can use binary search to find the largest number whose square is less than or equal to x.

Algorithm

1. Handle edge cases: x = 0 or x = 1
2. Binary search in range [1, x/2] (or [1, x] for safety)
3. For each mid, check if mid * mid <= x
4. If mid * mid == x, return mid
5. If mid * mid < x, search right half (but store mid as potential answer)
6. If mid * mid > x, search left half

public class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) return x;
        
        long left = 1, right = x;
        long result = 0;
        
        while (left <= right) {
            long mid = left + (right - left) / 2;
            long square = mid * mid;
            
            if (square == x) {
                return (int) mid;
            } else if (square < x) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return (int) result;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(log n) - Binary search
• Space Complexity: O(1) - Only using variables

Approach 3: Newton's Method (Fastest)

Intuition

Newton's method for finding roots converges very quickly. For finding √x, we solve f(r) = r² - x = 0.

The iteration formula is: r = (r + x/r) / 2

Algorithm

1. Start with initial guess r = x
2. Iterate: r = (r + x/r) / 2
3. Stop when r * r is close enough to x

public class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        
        long r = x;
        
        while (r * r > x) {
            r = (r + x / r) / 2;
        }
        
        return (int) r;
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(log n) - Newton's method converges quadratically
• Space Complexity: O(1) - Only using variables

Approach 4: Bit Manipulation

Intuition

Build the answer bit by bit, starting from the most significant bit.

public class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        
        long result = 0;
        long bit = 1L << 16;  // Start from a large power of 2
        
        while (bit > 0) {
            long temp = result | bit;
            if (temp * temp <= x) {
                result = temp;
            }
            bit >>= 1;
        }
        
        return (int) result;
    }
}

Complexity Analysis

• Time Complexity: O(log n) - 16 iterations for 32-bit integers
• Space Complexity: O(1) - Only using variables

Finding Square Root with Decimal Precision

Key Takeaways

1. Binary Search Application: Square root is a monotonic function, perfect for binary search
2. Integer Overflow: Use long long in C++ or long in Java to avoid overflow when squaring
3. Newton's Method: Provides faster convergence than binary search in practice
4. Search Space: For x >= 2, the square root is always <= x/2
5. Edge Cases: Handle x = 0 and x = 1 separately
6. Bit Manipulation: An elegant approach that builds the answer bit by bit
7. Precision: Can be extended to find decimal precision using similar techniques