Sqrt(x) - Integer Square Root

📋

Problem

Imagine you are designing a calculator app that needs to quickly find the integer square root of a large number without using built-in functions.

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. You must not use any built-in exponent function or operator.

0 ≤ x ≤ 2^31 - 1

Edge cases: x = 0 → output 0x = 1 → output 1x = 2147395599 (just below 46340^2) → output 46339

</>

IDE

def mySqrt(x: int) -> int:public int mySqrt(int x)int mySqrt(int x)function mySqrt(x)

def mySqrt(x: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int mySqrt(int x) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int mySqrt(int x) {
    // Write your solution here
    return 0;
}

function mySqrt(x) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Too large (e.g., 46340 for input 2147395599)Overflow in mid*mid calculation causing incorrect comparisons.✅ Cast mid to 64-bit integer before multiplication to avoid overflow.

Wrong: Off-by-one low (e.g., 1 for input 4)Not returning mid when mid*mid == x; binary search boundaries updated incorrectly.✅ Add condition to return mid immediately if mid*mid == x.

Wrong: Non-zero for input 0Missing base case for x=0; loop or binary search assumes x>0.✅ Add explicit check: if x == 0 return 0.

Wrong: Too slow or timeout on large inputUsing brute force linear search instead of binary search.✅ Implement binary search to reduce time complexity to O(log x).

✓

Test Cases

Focus on handling boundary inputs and zero cases correctly.

Test your code on perfect squares and maximum input values to catch subtle bugs.

Optimize your solution to run in logarithmic time to handle large inputs efficiently.

t1_01basic

Input{"x":8}

Expected2

⏱ Performance - must finish in 2000ms

The square root of 8 is approximately 2.82842, truncating decimal part gives 2.

💡 Think about searching for the integer whose square is just less than or equal to x.

💡 Use binary search between 0 and x to find the largest integer whose square is <= x.

💡 Check mid*mid <= x and adjust search boundaries accordingly.

Why it failed: Returned value too high or low due to incorrect binary search boundaries or off-by-one error. Fix by ensuring mid*mid <= x and adjusting low/high pointers properly.

✓ Correct integer square root found using binary search.

t1_02basic

Input{"x":15}

Expected3

⏱ Performance - must finish in 2000ms

Square root of 15 is about 3.8729, truncating decimal part gives 3.

💡 Try binary searching between 0 and x to find the integer sqrt.

💡 Remember to check mid*mid <= x to decide search direction.

💡 Adjust low and high pointers carefully to avoid missing the correct integer.

Why it failed: Incorrect output due to not properly handling the condition mid*mid <= x or off-by-one errors in updating search bounds.

✓ Binary search correctly finds integer sqrt truncation.

t2_01edge

Input{"x":0}

Expected0

⏱ Performance - must finish in 2000ms

Square root of 0 is 0.

💡 Check how your code handles the smallest input.

💡 Make sure to return 0 immediately or handle low boundary correctly.

💡 Avoid loops or searches that assume x > 0.

Why it failed: Fails on x=0 by returning non-zero or error due to missing base case. Fix by adding explicit check for x == 0 returning 0.

✓ Correctly handles zero input.

t2_02edge

Input{"x":1}

Expected1

⏱ Performance - must finish in 2000ms

Square root of 1 is 1.

💡 Check how your code handles the smallest positive input.

💡 Ensure that the binary search includes 1 as a valid answer.

💡 Avoid off-by-one errors that might skip 1.

Why it failed: Fails on x=1 by returning 0 or incorrect value due to off-by-one or boundary errors. Fix by ensuring low and high pointers include 1 and condition mid*mid <= x is checked properly.

✓ Correctly returns 1 for input 1.

t2_03edge

Input{"x":2147395599}

Expected46339

⏱ Performance - must finish in 2000ms

2147395599 is just below 46340^2; integer sqrt truncates to 46339.

💡 Test your code on large inputs near perfect squares.

💡 Watch for integer overflow when computing mid*mid.

💡 Use long or 64-bit integer types or cast to avoid overflow.

Why it failed: Incorrect output due to integer overflow in mid*mid calculation causing wrong comparisons. Fix by using 64-bit integer type or casting mid to long before multiplication.

✓ Correctly handles large inputs without overflow.

t3_01corner

Input{"x":2147483647}

Expected46340

⏱ Performance - must finish in 2000ms

Maximum 32-bit int; sqrt truncates to 46340.

💡 Test the maximum input value to check for overflow and correctness.

💡 Ensure your binary search handles upper boundary correctly.

💡 Use 64-bit integer for mid*mid to avoid overflow.

Why it failed: Fails due to overflow or incorrect boundary handling at max input. Fix by using 64-bit multiplication and correct binary search bounds.

✓ Correctly computes sqrt for max 32-bit integer input.

t3_02corner

Input{"x":4}

Expected2

⏱ Performance - must finish in 2000ms

Square root of 4 is exactly 2; tests exact boundary condition.

💡 Check how your code handles perfect squares.

💡 Ensure your binary search returns exact sqrt when mid*mid == x.

💡 Avoid off-by-one errors that might return mid-1 or mid+1 incorrectly.

Why it failed: Fails on perfect squares by returning incorrect floor value due to off-by-one error. Fix by returning mid immediately when mid*mid == x.

✓ Correctly returns exact sqrt for perfect squares.

t3_03corner

Input{"x":9}

Expected3

⏱ Performance - must finish in 2000ms

Square root of 9 is exactly 3; tests off-by-one errors in binary search.

💡 Test perfect squares to catch off-by-one errors.

💡 Check your binary search loop termination condition.

💡 Return mid when mid*mid == x to avoid off-by-one mistakes.

Why it failed: Fails due to off-by-one error returning 2 instead of 3 for perfect square 9. Fix by checking mid*mid == x and returning mid immediately.

✓ Correctly handles perfect square input without off-by-one error.

t4_01performance

Input{"x":2147483647}

Expectednull

⏱ Performance - must finish in 2000ms

Maximum input value x=2^31-1; binary search O(log x) must complete within 2 seconds.

💡 Use binary search to achieve O(log x) time complexity.

💡 Avoid brute force linear search which is O(√x) and too slow here.

💡 Implement efficient mid calculation and boundary updates.

Why it failed: TLE due to using brute force or inefficient approach with O(√x) or worse complexity. Fix by implementing binary search with O(log x) complexity.

✓ Efficient binary search implementation confirmed by passing performance test.

Practice

1. You are given two sorted arrays and need to find the median of their combined elements efficiently without merging them fully. Which approach best guarantees an optimal solution for this problem?

easy

A. Apply a binary search on the smaller array to find the correct partition point.

B. Use dynamic programming to store intermediate medians and combine results.

C. Merge both arrays completely and then pick the median element.

D. Use a greedy approach to pick elements from both arrays until the median is found.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the median without fully merging arrays to achieve better than O(m+n) time.

2. Step 2: Identify optimal approach

   Binary search on the smaller array partitions both arrays correctly to find median in O(log(min(m,n))) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on smaller array is classic optimal approach [OK]

Hint: Optimal median uses binary search on smaller array [OK]

Common Mistakes:

• Thinking merging arrays is optimal
• Using greedy selection without binary search
• Confusing DP with this problem

2. Consider the following buggy code snippet intended to find the first and last positions of a target in a sorted array. What is the bug?

medium

A. The binary search stops immediately after finding any occurrence, not the first or last

B. The initial values of start and end are incorrectly set

C. The mid calculation can cause overflow for large indices

D. The while loops expanding boundaries do not check array bounds before accessing indices

Solution

1. Step 1: Examine boundary expansion loops

   Loops check nums[start - 1] and nums[end + 1] without verifying indices are within array bounds.

2. Step 2: Identify potential index out of range error

   If start=0 or end=len(nums)-1, accessing start-1 or end+1 causes IndexError.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Boundary checks missing before array access [OK]

Hint: Always check array bounds before accessing neighbors [OK]

Common Mistakes:

• Stopping binary search early
• Ignoring boundary checks
• Incorrect mid calculation

3. What is the worst-case time complexity of the optimal modified binary search algorithm to find the minimum in a rotated sorted array with duplicates?

medium

A. O(n log n)

B. O(log n)

C. O(n)

D. O(1)

Solution

1. Step 1: Understand binary search with duplicates

   Duplicates can cause the algorithm to reduce high by one each iteration when nums[mid] == nums[high], leading to linear scan behavior.

2. Step 2: Analyze worst-case scenario

   In worst case (all elements equal), the algorithm degrades to O(n) because it may shrink high by one each time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Duplicates cause worst-case linear time [OK]

Hint: Duplicates cause worst-case linear time despite binary search [OK]

Common Mistakes:

• Assuming always O(log n)
• Confusing average and worst case

4. What is the time complexity of the optimal binary search solution for finding the smallest divisor given an array of size n and maximum element max_num?

medium

A. O(n + log max_num)

B. O(n * max_num)

C. O(log n * max_num)

D. O(n log max_num)

Solution

1. Step 1: Identify the binary search iterations

   Binary search runs over the range [1, max_num], so it takes O(log max_num) steps.

2. Step 2: Analyze the feasibility check cost

   Each feasibility check sums over all n elements, costing O(n).

3. Step 3: Combine complexities

   Total time is O(n * log max_num), since feasibility is done each binary search iteration.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Binary search log factor times linear feasibility -> [OK]

Hint: Binary search log factor times linear feasibility check [OK]

Common Mistakes:

• Confusing max_num with n in complexity
• Forgetting feasibility check cost per iteration
• Assuming linear search complexity applies

5. Suppose the array can contain duplicate elements and the problem is modified so that elements can be reused multiple times when selecting the k closest elements to x. Which modification to the optimal binary search approach is necessary to handle this variant correctly?

hard

A. Use a priority queue to repeatedly pick the closest element allowing duplicates, instead of binary search.

B. Modify binary search to consider overlapping windows and allow repeated elements in the window.

C. No change needed; the existing binary search on window boundaries works as is.

D. Switch to a dynamic programming approach to track counts of reused elements.

Solution

1. Step 1: Understand reuse of elements

   Allowing reuse means the window concept breaks because elements can appear multiple times, invalidating fixed window binary search.

2. Step 2: Identify suitable approach

   A priority queue (min-heap) can repeatedly select the closest element to x, allowing duplicates and dynamic selection.

3. Step 3: Why other options fail

   Binary search on windows assumes unique elements and fixed windows; DP is unnecessary and inefficient here.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Priority queue supports repeated selection, unlike fixed window binary search [OK]

Hint: Reuse breaks fixed window; priority queue handles duplicates [OK]

Common Mistakes:

• Assuming binary search window works with reuse
• Overcomplicating with DP when simpler heap suffices
• Ignoring duplicates in window boundaries