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 an unsorted array of integers and need to find an index of an element that is greater than its neighbors (or boundary elements if at edges). Which algorithmic approach guarantees an optimal O(log n) time solution for this problem?

easy

A. Linear scan checking each element and its neighbors sequentially

B. Dynamic programming to store and compare local maxima

C. Modified binary search that compares middle element with its right neighbor to decide search direction

D. Greedy approach selecting the first element larger than the previous one

Solution

1. Step 1: Understand problem constraints

   The problem requires finding a peak element efficiently, which suggests a logarithmic time approach.

2. Step 2: Identify algorithm matching O(log n) time

   Modified binary search that compares mid element with its neighbor to decide which half to search next achieves O(log n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search halves search space each step [OK]

Hint: Peak element search uses modified binary search [OK]

Common Mistakes:

• Assuming greedy or DP solves this optimally
• Confusing linear scan as optimal
• Using DP unnecessarily

2. You are given an array representing the days on which flowers bloom. You want to make m bouquets, each consisting of k adjacent flowers. What is the most efficient approach to find the minimum day by which you can make all bouquets?

easy

A. Apply binary search on the range of days and check feasibility for each mid value.

B. Use a greedy approach to pick the earliest blooming flowers until bouquets are formed.

C. Use dynamic programming to track the minimum days for each bouquet count.

D. Sort the bloom days and pick the first m*k flowers directly.

Solution

1. Step 1: Understand the problem constraints

   We need to find the minimum day such that we can form m bouquets of k adjacent flowers. The days range from min to max bloom day.

2. Step 2: Recognize the pattern

   Binary searching over the answer space (days) and checking feasibility for each candidate day efficiently narrows down the minimum day. Greedy or sorting alone do not guarantee correctness because adjacency and feasibility must be checked.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on answer space is the standard pattern for such minimum day feasibility problems. [OK]

Hint: Binary search on answer space fits minimum day feasibility problems [OK]

Common Mistakes:

• Thinking greedy or sorting alone solves adjacency constraints
• Using DP unnecessarily complicates the problem

3. Examine the following buggy code for finding the single non-duplicate element in a sorted array. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line 11: updating high to mid - 1 may skip the single element

B. Line 5: parity check on mid is incorrect for odd indices

C. Line 7: comparison with nums[mid + 1] can cause index out of range

D. Line 3: mid calculation uses division without floor, resulting in float index

Solution

1. Step 1: Identify mid calculation issue

   Using '/' in Python 3 returns float, which cannot index arrays, causing errors or infinite loops.

2. Step 2: Confirm other lines are correct

   Parity checks and updates are correct; no out-of-range access due to loop conditions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   mid must be integer index; float causes failure [OK]

Hint: mid must be integer index, not float [OK]

Common Mistakes:

• Using '/' instead of '//' in Python 3
• Confusing parity logic
• Incorrect boundary updates

4. Suppose the problem is modified so that the matrix rows are sorted but columns are not guaranteed to be sorted. Which approach would correctly find the kth smallest element efficiently?

hard

A. Use the min-heap approach merging rows as before, since rows remain sorted.

B. Flatten the matrix and sort it, then return the kth element.

C. Use binary search on the value range with a counting function scanning the entire matrix.

D. Use a min-heap merging columns instead of rows.

Solution

1. Step 1: Analyze matrix properties

   Rows are sorted but columns are not, so min-heap merging rows only partially orders elements.

2. Step 2: Evaluate approaches

   Min-heap merging rows assumes columns sorted for correctness; binary search counting requires sorted rows and columns for efficient counting; flatten and sort works regardless.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Flatten and sort is the fallback when only rows sorted [OK]

Hint: Partial sorting breaks heap and binary search assumptions [OK]

Common Mistakes:

• Assuming min-heap merging rows still works
• Using binary search counting without full sorting
• Ignoring matrix sorting properties

5. Suppose the problem is modified so that balls can be placed multiple times at the same position (reuse allowed). Which modification to the algorithm is correct to find the maximum minimum distance?

hard

A. Keep the same binary search and greedy feasibility check since reuse does not affect placement logic

B. Modify feasibility check to count balls without updating last_pos when reuse occurs

C. Replace binary search with a linear search over all distances due to reuse complexity

D. Use dynamic programming to handle multiple placements at the same position

Solution

1. Step 1: Understand reuse impact

   Allowing reuse means multiple balls can be placed at the same position, so distance between balls can be zero.

2. Step 2: Modify feasibility check

   The greedy check must count balls even if distance is zero, but only update last_pos when distance condition is met to avoid infinite loops.

3. Step 3: Binary search remains valid

   Binary search on answer space still applies, but feasibility check logic must adapt to reuse.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Feasibility check must handle reuse carefully [OK]

Hint: Reuse breaks distance check; feasibility must count balls differently [OK]

Common Mistakes:

• Assuming reuse doesn't change feasibility check
• Switching to linear search unnecessarily