Sqrt(x) - Integer Square Root

▶

Steps

setup

Check if x < 2

The algorithm checks if the input x is less than 2. Since x=8, it proceeds to the next step.

💡 This step handles trivial cases quickly, avoiding unnecessary computation.

Line:

if x < 2:
    return x

💡 We know x=8 requires iterative guessing.

setup

Initialize guess to x // 2

The initial guess is set to 4 (8 // 2). This is the starting point for iterative refinement.

💡 Starting at half of x is a reasonable initial guess to speed up convergence.

Line:

guess = x // 2

💡 The guess is within the possible integer root range.

compare

Check if guess*guess > x

Check if 4*4 = 16 is greater than 8. It is, so the guess is too high and must be decreased.

💡 This comparison tells us if the guess is an overestimate.

Line:

while guess * guess > x:

💡 We need to reduce the guess to get closer to the integer root.

shrink

Update guess using Newton's formula

Update guess to (4 + 8 // 4) // 2 = (4 + 2) // 2 = 3. This is a better approximation.

💡 Newton's method refines the guess by averaging it with x divided by guess.

Line:

guess = (guess + x // guess) // 2

💡 The guess moves closer to the true integer root.

compare

Check if guess*guess > x again

Check if 3*3 = 9 is greater than 8. It is, so guess is still too high.

💡 We verify if the new guess is still an overestimate.

Line:

while guess * guess > x:

💡 Guess needs further refinement.

shrink

Update guess again using Newton's formula

Update guess to (3 + 8 // 3) // 2 = (3 + 2) // 2 = 2. This guess is closer to the integer root.

💡 Each update moves guess closer to the true root by averaging.

Line:

guess = (guess + x // guess) // 2

💡 Guess is now 2, which may be the integer root.

compare

Check if guess*guess > x

Check if 2*2 = 4 is greater than 8. It is not, so the loop condition fails and we stop updating guess.

💡 This check determines if the current guess is a valid integer root approximation.

Line:

while guess * guess > x:

💡 Guess is now less than or equal to the integer root.

compare

Verify guess+1 squared is greater than x

Check if (2+1)*(2+1) = 9 is greater than 8. It is, confirming guess=2 is the integer square root truncation.

💡 This final check ensures guess is the largest integer whose square is <= x.

Line:

return guess  # after loop ends

💡 Guess 2 is the correct integer square root.

reconstruct

Prepare to return the final guess

The algorithm prepares to return 2 as the integer square root of 8, truncating the decimal part.

💡 This step confirms the final guess before returning.

Line:

return guess

💡 The integer square root is 2 for input 8.

reconstruct

Return the final guess

The algorithm returns 2 as the integer square root of 8, completing the computation.

💡 Returning the guess completes the algorithm.

Line:

return guess

💡 The integer square root is 2 for input 8.

def mySqrt(x: int) -> int:
    # STEP 1: Handle trivial cases
    if x < 2:
        return x
    # STEP 2: Initialize guess
    guess = x // 2
    # STEP 3-7: Iteratively refine guess
    while guess * guess > x:
        # STEP 4 & 6: Update guess using Newton's method
        guess = (guess + x // guess) // 2
    # STEP 9 & 10: Return final guess
    return guess

if __name__ == '__main__':
    print(mySqrt(8))  # Output: 2

📊

Sqrt(x) - Integer Square Root - Watch the Algorithm Execute, Step by Step

Watching each guess update and comparison helps you understand how the algorithm converges quickly to the correct integer square root without checking every number.

Target: 8

1

0

lo

2

1

3

2

4

3

Next: lo=1 hi=4

Target: 8

1

0

lo

2

1

3

2

4

3

Next: lo=1 hi=4

Target: 8

1

0

lo

2

1

3

2

4

3

Next: lo=1 hi=3

Target: 8

1

0

lo

2

1

3

2

mid/hi

4

3

mid[3]=3 - guess squared = 9 > 8

Next: lo=1 hi=3

Target: 8

1

0

lo

2

1

3

2

mid/hi

4

3

mid[3]=3 - 9 > 8, guess too high

Next: lo=1 hi=2

Target: 8

1

0

lo

2

1

mid/hi

3

2

4

3

mid[2]=2 - guess squared = 4 <= 8

Next: lo=1 hi=2

Target: 8

1

0

lo

2

1

mid/hi

3

2

4

3

mid[2]=2 - 4 <= 8, guess valid

Next: lo=1 hi=2

Target: 8

1

0

lo

2

1

mid/hi

3

2

4

3

mid[2]=2 - 4 <= 8 and 9 > 8, guess confirmed

Next: lo=1 hi=2

Target: 8

1

0

lo

2

1

mid/hi

3

2

4

3

mid[2]=2 - final answer confirmed

Next: lo=1 hi=2

Target: 8

1

0

lo

2

1

mid/hi

3

2

4

3

mid[2]=2 - final answer

Next: lo=1 hi=2

Key Takeaways

✓ Newton's method quickly converges to the integer square root by iteratively refining the guess.

Reading code alone doesn't show how fast the guess improves; watching each update reveals the efficiency.

✓ The stopping condition ensures the guess is the largest integer whose square is less than or equal to x.

Understanding the condition guess*guess <= x < (guess+1)*(guess+1) is easier when seen step-by-step.

✓ Each guess update eliminates a large portion of the search space, similar to binary search narrowing.

Visualizing eliminated regions clarifies how the algorithm prunes impossible guesses efficiently.

Practice

1. You are given a sorted array that has been rotated at an unknown pivot and may contain duplicates. You need to determine if a target value exists in this array efficiently. Which approach best guarantees an optimal average-case runtime while correctly handling duplicates?

easy

A. Use a simple linear scan through the array to find the target.

B. Apply a modified binary search that skips duplicates from both ends before deciding which half to search.

C. Use a classic binary search assuming no duplicates and no rotation.

D. Apply a dynamic programming approach to track possible target positions.

Solution

1. Step 1: Understand problem constraints

   The array is rotated and contains duplicates, which breaks classic binary search assumptions.

2. Step 2: Identify approach handling duplicates and rotation

   Modified binary search that skips duplicates at both ends before deciding the sorted half ensures correctness and efficiency.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Duplicates cause ambiguity; skipping them resolves it [OK]

Hint: Skip duplicates at boundaries before binary search [OK]

Common Mistakes:

• Assuming classic binary search works with duplicates
• Using DP unnecessarily
• Relying on linear scan for efficiency

2. You are given a sorted array and a target value. You need to find the index where the target should be inserted to maintain the sorted order. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Greedy approach that inserts the target at the first position where the next element is larger

B. Linear scan from the start to find the first element greater than or equal to the target

C. Dynamic programming that builds solutions for subproblems of smaller arrays

D. Binary search that repeatedly halves the search space to find the correct insertion index

Solution

1. Step 1: Understand problem constraints

   The array is sorted, so searching can be optimized by halving the search space instead of scanning linearly.

2. Step 2: Identify the algorithm that efficiently finds insertion index

   Binary search divides the array repeatedly, guaranteeing O(log n) time, which is optimal compared to linear or DP approaches.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Binary search is the classic approach for sorted array search problems [OK]

Hint: Sorted array + insertion -> binary search [OK]

Common Mistakes:

• Assuming greedy insertion is always optimal
• Confusing DP with binary search
• Using linear scan despite sorted input

3. Consider the following Python code implementing the optimal solution for splitting an array into m subarrays minimizing the largest sum. Given nums = [7, 2, 5, 10] and m = 2, what is the final returned value?

easy

A. 10

B. 12

C. 17

D. 15

Solution

1. Step 1: Calculate prefix sums

   prefix = [0, 7, 9, 14, 24]

2. Step 2: Binary search on answer space [7,24]

   Check mid=15: can split into subarrays with max sum ≤15? Yes (e.g., [7,2,5] and [10]). Try lower mid=11: cannot split into 2 subarrays with max sum ≤11. Finally, minimal largest sum found is 12.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Minimal largest sum for splitting [7,2,5,10] into 2 parts is 12 [OK]

Hint: Trace binary search mid and feasibility check carefully [OK]

Common Mistakes:

• Off-by-one in bisect leading to wrong subarray boundaries
• Confusing max element with sum for low/high bounds
• Miscounting number of splits in feasibility check

4. Suppose the problem is modified so that the two input arrays can contain duplicate elements and you want to find the median of the combined multiset where elements can be reused infinitely many times. Which modification to the binary search on value range approach correctly handles this scenario?

hard

A. Modify countLessEqual to count elements less or equal normally, but adjust total length to infinite, then return left directly.

B. Use the same binary search on value range but count elements less or equal considering infinite duplicates as infinite count.

C. Use binary search on value range with countLessEqual unchanged, but adjust the target count to half of the finite combined length ignoring duplicates.

D. Use binary search on value range with countLessEqual unchanged, but since duplicates are infinite, the median is the minimum element.

Solution

1. Step 1: Understand infinite duplicates impact

   Infinite duplicates mean total length is infinite, so median is the smallest value with countLessEqual ≥ half of infinite.

2. Step 2: Adjust countLessEqual and target

   Counting elements normally but total length infinite means target is infinite/2 = infinite, so median is left boundary where countLessEqual reaches infinite.

3. Step 3: Return left directly

   Since infinite duplicates, median is the smallest value that satisfies countLessEqual condition, so return left.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Infinite duplicates require adjusting total length and returning left [OK]

Hint: Infinite duplicates make total length infinite, median is smallest qualifying value [OK]

Common Mistakes:

• Counting duplicates as finite
• Ignoring infinite total length
• Returning min element incorrectly

5. Suppose the array can contain duplicate elements and you want to find the first position where the target can be inserted (i.e., the leftmost insertion point). Which modification to the binary search algorithm correctly achieves this?

hard

A. When nums[mid] >= target, recurse on the left half; else recurse on the right half.

B. Change the base case to return right instead of left when left > right.

C. When nums[mid] > target, recurse on the right half; else recurse on the left half.

D. Use linear scan after binary search to find the first occurrence.

Solution

1. Step 1: Understand requirement for leftmost insertion

   We must find the earliest index where target can be inserted, including duplicates.

2. Step 2: Modify binary search condition

   If nums[mid] >= target, recurse left to find earlier occurrence; else recurse right.

3. Step 3: Avoid linear scan for efficiency

   Linear scan after binary search defeats O(log n) goal.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Condition ensures leftmost insertion index found efficiently [OK]

Hint: For leftmost insert, recurse left on >= target [OK]

Common Mistakes:

• Recursing right on >= target misses leftmost index
• Returning right instead of left at base case
• Using linear scan after binary search