Sqrt(x) - Integer Square Root

🎯

Sqrt(x) - Integer Square Root

easyBINARY_SEARCHAmazonGoogleBloomberg

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.

💡 This problem asks for the integer square root, which means the largest integer whose square is less than or equal to the input. Beginners often struggle because they try to use floating-point math or get off-by-one errors when searching for the correct 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. You must not use any built-in exponent function or operator.

0 ≤ x ≤ 2^31 - 1

💡

Example

Input"x = 8"

Output2

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

• x = 0 → output 0
• x = 1 → output 1
• x = 2147395599 (just below 46340^2) → output 46339
• x = 2147483647 (max 32-bit int) → output 46340

⚠️

Common Mistakes

Not handling x=0 or x=1 as special cases

Incorrect output or infinite loop

✅ Add explicit checks for x < 2 returning x

Integer overflow when computing mid*mid

Wrong comparisons leading to incorrect answer or runtime error

✅ Use long/long long or cast to larger type before multiplication

Off-by-one errors in binary search boundaries

Returns incorrect integer square root (too high or too low)

✅ Carefully update low and high pointers and track answer correctly

Using floating point division or math.sqrt()

Violates problem constraints and may cause precision errors

✅ Use integer arithmetic only and avoid built-in sqrt functions

Infinite loop in Newton's method due to incorrect update or stopping condition

Code never terminates

✅ Ensure guess updates and loop condition correctly reduce guess until convergence

🧠

Brute Force (Linear Search)

💡 This approach exists to build intuition by trying every possible integer from 0 upwards until the square exceeds x. It is simple but inefficient, helping beginners understand the problem's nature.

Intuition

Start from 0 and incrementally check each integer's square until it surpasses x. The answer is the last integer whose square is less than or equal to x.

Algorithm

1. Initialize a variable i to 0.
2. While i*i is less than or equal to x, increment i.
3. Return i-1 as the integer square root.

💡 The main challenge is realizing that the answer is the last i before i*i exceeds x, which is easy to miss.

</>

Code

def mySqrt(x: int) -> int:
    i = 0
    while i * i <= x:
        i += 1
    return i - 1

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

Line Notes

i = 0Initialize the candidate integer to start checking from zero

while i * i <= x:Check if the square of i is still within the limit x

i += 1Increment i to test the next integer

return i - 1Return the last integer whose square did not exceed x

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

    public static void main(String[] args) {
        System.out.println(mySqrt(8)); // Output: 2
    }
}

Line Notes

int i = 0;Start checking from zero

while ((long)i * i <= x)Use long to avoid integer overflow when squaring

i++;Increment candidate integer

return i - 1;Return last valid integer square root

#include <iostream>
using namespace std;

int mySqrt(int x) {
    int i = 0;
    while ((long long)i * i <= x) {
        i++;
    }
    return i - 1;
}

int main() {
    cout << mySqrt(8) << endl; // Output: 2
    return 0;
}

Line Notes

int i = 0;Initialize candidate integer

while ((long long)i * i <= x)Cast to long long to prevent overflow when squaring

i++;Increment candidate integer

return i - 1;Return last integer whose square is <= x

function mySqrt(x) {
    let i = 0;
    while (i * i <= x) {
        i++;
    }
    return i - 1;
}

// Test
console.log(mySqrt(8)); // Output: 2

Line Notes

let i = 0;Initialize candidate integer

while (i * i <= x)Check if square is within limit

i++;Increment candidate integer

return i - 1;Return last valid integer square root

⏱

Complexity

TimeO(√ x)

SpaceO(1)

We increment i until i*i > x, which takes roughly √ x steps.

💡 For x=10,000, this means about 100 steps, which is okay but slow for very large x.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but helps understand the problem before optimizing.

🧠

Binary Search (Classic)

💡 Binary search is a natural fit because the square root lies between 0 and x, and we can efficiently narrow down the range by comparing mid*mid to x.

Intuition

Use binary search on the range [0, x]. At each step, check if mid*mid is less than, equal to, or greater than x to decide which half to search next.

Algorithm

1. Set low = 0 and high = x.
2. While low <= high, compute mid = (low + high) // 2.
3. If mid*mid == x, return mid.
4. If mid*mid < x, move low to mid + 1 and record mid as potential answer.
5. Else, move high to mid - 1.
6. Return the recorded answer.

💡 The key is to track the last mid whose square was less than or equal to x to handle cases where x is not a perfect square.

</>

Code

def mySqrt(x: int) -> int:
    if x < 2:
        return x
    low, high = 0, x
    ans = 0
    while low <= high:
        mid = (low + high) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            ans = mid
            low = mid + 1
        else:
            high = mid - 1
    return ans

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

Line Notes

if x < 2:Handle small inputs quickly

low, high = 0, xInitialize binary search boundaries

while low <= high:Loop until search space is exhausted

mid = (low + high) // 2Find middle element to test

if mid * mid == x:Check for exact square root

elif mid * mid < x:Mid is too small, move low up and record mid

else:Mid is too large, move high down

return ansReturn the best candidate found

public class Solution {
    public static int mySqrt(int x) {
        if (x < 2) return x;
        int low = 0, high = x, ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            long sq = (long)mid * mid;
            if (sq == x) return mid;
            else if (sq < x) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(mySqrt(8)); // Output: 2
    }
}

Line Notes

if (x < 2) return x;Quickly handle small inputs

int low = 0, high = x, ans = 0;Initialize binary search variables

while (low <= high)Loop until search space exhausted

int mid = low + (high - low) / 2;Calculate mid to avoid overflow

long sq = (long)mid * mid;Use long to prevent overflow when squaring

if (sq == x) return mid;Exact square root found

else if (sq < x)Mid too small, update answer and move low up

elseMid too large, move high down

return ans;Return best candidate

#include <iostream>
using namespace std;

int mySqrt(int x) {
    if (x < 2) return x;
    int low = 0, high = x, ans = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        long long sq = (long long)mid * mid;
        if (sq == x) return mid;
        else if (sq < x) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

int main() {
    cout << mySqrt(8) << endl; // Output: 2
    return 0;
}

Line Notes

if (x < 2) return x;Handle small inputs quickly

int low = 0, high = x, ans = 0;Initialize binary search variables

while (low <= high)Loop until search space exhausted

int mid = low + (high - low) / 2;Calculate mid to avoid overflow

long long sq = (long long)mid * mid;Use long long to prevent overflow

if (sq == x) return mid;Exact square root found

else if (sq < x)Mid too small, update answer and move low up

elseMid too large, move high down

return ans;Return best candidate

function mySqrt(x) {
    if (x < 2) return x;
    let low = 0, high = x, ans = 0;
    while (low <= high) {
        let mid = Math.floor(low + (high - low) / 2);
        let sq = mid * mid;
        if (sq === x) return mid;
        else if (sq < x) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

// Test
console.log(mySqrt(8)); // Output: 2

Line Notes

if (x < 2) return x;Handle small inputs quickly

let low = 0, high = x, ans = 0;Initialize binary search variables

while (low <= high)Loop until search space exhausted

let mid = Math.floor(low + (high - low) / 2);Calculate mid to avoid overflow

let sq = mid * mid;Calculate square of mid

if (sq === x) return mid;Exact square root found

else if (sq < x)Mid too small, update answer and move low up

elseMid too large, move high down

return ans;Return best candidate

⏱

Complexity

TimeO(log x)

SpaceO(1)

Binary search halves the search space each iteration, so it takes about log2(x) steps.

💡 For x=10^9, this means about 30 steps, which is very efficient.

Interview Verdict: Accepted

This is the standard efficient solution expected in interviews.

🧠

Newton's Method (Fast Convergence)

💡 Newton's method uses calculus to approximate roots quickly. It converges faster than binary search but requires understanding of derivatives and iterative refinement.

Intuition

Start with a guess and iteratively improve it using the formula: new_guess = (guess + x / guess) // 2 until convergence.

Algorithm

1. If x < 2, return x immediately.
2. Initialize guess to x // 2.
3. Iteratively update guess to (guess + x // guess) // 2.
4. Stop when guess*guess <= x and (guess+1)*(guess+1) > x.
5. Return guess.

💡 The key is the iterative formula that rapidly improves the guess, and the stopping condition ensures the integer square root is found.

</>

Code

def mySqrt(x: int) -> int:
    if x < 2:
        return x
    guess = x // 2
    while guess * guess > x:
        guess = (guess + x // guess) // 2
    return guess

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

Line Notes

if x < 2:Handle small inputs quickly

guess = x // 2Start with a reasonable initial guess

while guess * guess > x:Continue refining while guess is too large

guess = (guess + x // guess) // 2Update guess using Newton's formula

return guessReturn the integer square root

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

    public static void main(String[] args) {
        System.out.println(mySqrt(8)); // Output: 2
    }
}

Line Notes

if (x < 2) return x;Handle small inputs quickly

long guess = x / 2;Initial guess as half of x

while (guess * guess > x)Refine guess while too large

guess = (guess + x / guess) / 2;Newton's update formula

return (int)guess;Cast back to int for result

#include <iostream>
using namespace std;

int mySqrt(int x) {
    if (x < 2) return x;
    long long guess = x / 2;
    while (guess * guess > x) {
        guess = (guess + x / guess) / 2;
    }
    return (int)guess;
}

int main() {
    cout << mySqrt(8) << endl; // Output: 2
    return 0;
}

Line Notes

if (x < 2) return x;Handle small inputs quickly

long long guess = x / 2;Initial guess as half of x

while (guess * guess > x)Refine guess while too large

guess = (guess + x / guess) / 2;Newton's update formula

return (int)guess;Cast back to int for result

function mySqrt(x) {
    if (x < 2) return x;
    let guess = Math.floor(x / 2);
    while (guess * guess > x) {
        guess = Math.floor((guess + Math.floor(x / guess)) / 2);
    }
    return guess;
}

// Test
console.log(mySqrt(8)); // Output: 2

Line Notes

if (x < 2) return x;Handle small inputs quickly

let guess = Math.floor(x / 2);Initial guess as half of x

while (guess * guess > x)Refine guess while too large

guess = Math.floor((guess + Math.floor(x / guess)) / 2);Newton's update formula

return guess;Return integer square root

⏱

Complexity

TimeO(log x)

SpaceO(1)

Newton's method converges quadratically, so it typically requires fewer iterations than binary search.

💡 For large x, this method quickly zeroes in on the answer in very few steps.

Interview Verdict: Accepted

This is a fast and elegant solution, but requires understanding of Newton's method.

📊

All Approaches - One-Glance Tradeoffs

💡 Binary search is the best approach to implement in 95% of interviews due to its clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(√ x)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Binary Search	O(log x)	O(1)	No	N/A	Code this approach in interviews
3. Newton's Method	O(log x) (faster convergence)	O(1)	No	N/A	Mention as an optimization if comfortable with math

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain your reasoning clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Explain the binary search approach as the optimal solution.Step 4: Optionally mention Newton's method for further optimization.Step 5: Code the binary search solution carefully, handling edge cases.Step 6: Test your code with sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

The interviewer tests your problem understanding, ability to optimize from brute force to binary search, handling of edge cases, and clean coding skills.

Common Follow-ups

• How would you handle very large inputs without overflow? → Use long or 64-bit integers.
• Can you implement this without multiplication? → Use addition or bit shifts with more complex logic.

💡 These follow-ups test your attention to detail and ability to adapt your solution to constraints.

🔍

Pattern Recognition

When to Use

1. Problem asks for integer square root or similar root-finding. 2. Input is a single integer with large range. 3. Direct computation or built-in functions are disallowed. 4. You can leverage monotonicity to apply binary search.

Signature Phrases

'return the integer part of the square root''without using built-in exponent function or operator'

NOT This Pattern When

Problems that require floating-point precision or direct formula application are not this pattern.

Similar Problems

Find Peak Element - uses binary search on answer spaceSearch Insert Position - binary search variantPow(x, n) - uses binary search or fast exponentiation

Practice

1. You are given an array of positive integers and a threshold value. You want to find the smallest integer divisor such that when each array element is divided by this divisor and rounded up, the sum of these results does not exceed the threshold. Which algorithmic approach guarantees finding this smallest divisor efficiently?

easy

A. Greedy approach that picks divisors based on local minimum sums without backtracking

B. Dynamic programming to explore all divisor combinations and sums

C. Binary search on the divisor value combined with a feasibility check function

D. Sorting the array and using two pointers to find the divisor

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the smallest divisor that satisfies a sum condition involving ceiling division, which is monotonic with respect to the divisor.

2. Step 2: Identify the suitable algorithmic pattern

   Binary search on the answer space (divisor values) combined with a helper feasibility function efficiently narrows down the smallest divisor by checking if a candidate divisor meets the threshold condition.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search exploits monotonicity of feasibility -> [OK]

Hint: Monotonic feasibility suggests binary search on answer space [OK]

Common Mistakes:

• Assuming greedy local choices yield global minimum divisor
• Trying DP which is inefficient and unnecessary here
• Using sorting and two pointers which don't apply to divisor search

2. You are given an n x n matrix where each row and each column is sorted in ascending order. You need to find the kth smallest element in the matrix efficiently. Which of the following approaches guarantees the optimal time complexity for this problem?

easy

A. Use a greedy approach by repeatedly picking the smallest element from the matrix without extra data structures.

B. Flatten the matrix into a list, sort it, and return the kth element.

C. Apply dynamic programming to build a table of smallest elements up to k.

D. Use a min-heap to merge the sorted rows, extracting the smallest elements until the kth is found.

Solution

1. Step 1: Understand problem constraints

   The matrix rows and columns are sorted, so each row is sorted and each column is sorted independently.

2. Step 2: Identify the optimal approach

   Using a min-heap to merge sorted rows efficiently extracts the smallest elements in ascending order, achieving O(k log n) time, better than flattening and sorting.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Min-heap merges sorted lists optimally [OK]

Hint: Min-heap merges sorted rows efficiently [OK]

Common Mistakes:

• Assuming flatten and sort is optimal
• Confusing DP with this problem
• Thinking greedy without data structures works

3. Consider the following buggy code for finding a peak element. Which line contains the subtle bug that can cause incorrect results or infinite recursion?

def findPeakElement(nums):
    def binarySearch(low, high):
        if low == high:
            return low
        mid = (low + high) // 2
        if nums[mid] < nums[mid]:  # Line X
            return binarySearch(mid + 1, high)
        else:
            return binarySearch(low, mid)
    return binarySearch(0, len(nums) - 1)

medium

A. Line 5: if nums[mid] < nums[mid]:

B. Line 4: mid = (low + high) // 2

C. Line 3: if low == high: return low

D. Line 7: return binarySearch(low, mid)

Solution

1. Step 1: Identify suspicious comparison

   Line 5 compares nums[mid] with itself, which is always false, causing wrong recursion path.

2. Step 2: Understand impact

   This bug causes infinite recursion or incorrect peak detection because the condition never triggers correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Comparison must be nums[mid] < nums[mid + 1] [OK]

Hint: Check comparisons carefully for off-by-one errors [OK]

Common Mistakes:

• Comparing mid with mid instead of mid+1
• Off-by-one causing infinite recursion
• Returning wrong index after recursion

4. Suppose you want to find the first occurrence of a target value in a sorted array that may contain duplicates. Which modification to the classic binary search algorithm correctly achieves this?

hard

A. Return the first index where nums[mid] == target and check if previous element is different or mid == 0

B. Return any index where nums[mid] == target without further checks

C. Use linear search after binary search to find first occurrence

D. Modify binary search to always move low to mid + 1 when nums[mid] == target

Solution

1. Step 1: Understand problem with duplicates

   Classic binary search returns any matching index, not necessarily first occurrence.

2. Step 2: Modify binary search to check if mid is first occurrence

   When nums[mid] == target, check if mid == 0 or nums[mid-1] != target; if not, continue searching left half.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ensures first occurrence by verifying previous element [OK]

Hint: Check previous element to find first occurrence [OK]

Common Mistakes:

• Returning any occurrence
• Linear search after binary search wastes time
• Moving low forward on match loses first occurrence

5. Suppose the problem is modified so that the input array arr can contain negative numbers and zero, and you still need to find the kth positive missing number (positive integers missing from the array). Which of the following changes to the optimal binary search approach is correct?

hard

A. Modify the missing count calculation to be arr[mid] - (mid + 1) + offset, where offset accounts for negative numbers.

B. No change needed; the existing binary search works as is because it only depends on indices and values.

C. Filter out non-positive numbers first, then apply the binary search approach on the filtered positive array.

D. Use the brute force linear scan approach instead, as binary search cannot handle negative numbers.

Solution

1. Step 1: Understand the problem modification

   Negative numbers and zero do not affect the count of missing positive integers, but they disrupt the assumption that arr contains only positive sorted numbers.

2. Step 2: Adjust the input for binary search

   Filtering out non-positive numbers creates a sorted array of positive integers, restoring the problem's original assumptions and enabling correct binary search.

3. Step 3: Reject other options

   No change (B) fails because negative numbers break missing count logic; offset (C) is ambiguous and error-prone; brute force (D) is inefficient and unnecessary.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Filtering preserves correctness and efficiency [OK]

Hint: Filter positives before binary search [OK]

Common Mistakes:

• Assuming binary search works without filtering
• Trying to adjust missing count with offsets
• Switching to brute force unnecessarily