The O(n) Club: Cracking Integer Sqrt(x) Like a (Java) Boss

The O(n) Club: Cracking Integer Sqrt(x) Like a (Java) Boss

⚡ TL;DR

Don’t use Math.sqrt(). Don’t dare touch floats. Compute the integer square root of x—the biggest whole number whose square doesn’t leap over x—using binary search, not medieval for-loops. Example of what not to do:

// O(n) && O(monotony). Please don't.
public int mySqrt(int x) {
    for (int i = 0; i <= x; i++) {
        if ((long)i * i > x) return i - 1;
    }
    return x;
}

🧠 How Devs Usually Mess This Up

Classic mistakes? Buckle up. People:

• Panic and use Math.sqrt, then cast to int (the “that’ll trick the grader” approach)
• Ignore edge cases like x == 0 or x == 1—the two integers with commitment issues
• Multiply mid * mid without a care, causing integer overflow explosions (and some tears)
• Write an O(n) loop that’d be fine for x = 9, but melts for x = 2,147,483,647
• Fret about decimal results—seriously, it’s always floor, never round

🔍 What’s Actually Going On

Picture this: You’re on a staircase where each step is the square of its number. Step 4? Height: 16 units. Your goal? Climb as high as you can without busting your head—meaning, without landing on a square that overshoots x. That’s integer sqrt in a nutshell. The binary search approach is like being teleported straight up and down the staircase until you land exactly at or just below x, saving yourself a lot of unnecessary steps (and wear on your developer knees).

And in Java, since multiplying giant integers is basically the code version of Icarus flying into the sun, use x / mid instead of mid * mid to check if you’ve gone too high. Much safer. Much less crispy.

🛠️ PseudoCode

• Handle dull (edge) cases first:
  

  if (x == 0 || x == 1) return x;

• Set up your search bounds:
  

  int low = 1, high = x;

• Binary search loop:
  

  while (low <= high)

  • Calculate mid carefully:
    int mid = low + (high - low) / 2;
  • If mid <= x / mid, move low up, save the guess
    ans = mid; low = mid + 1;
  • Else, move high down:
    high = mid - 1;
• Return ans—largest integer whose square <= x.
  Simple. Painless. (Satisfyingly bug-proof.)

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

• Overflow: mid * mid makes your answer wrong or your code crash (silently!) for big x. Use division.
• Edge Cases: x == 0 and x == 1 need to be handled before the binary search or your code trips at the first step.
• Performance: O(log x) time, so you’re not accidentally running an algorithm that’s secretly a sleep aid.
• Space Complexity: No arrays. No fancy objects. Just simple, flat O(1) space.

🧠 Interviewer Brain-Tattoo

“When in doubt, divide it out: (mid <= x / mid) saves you from overflow drama AND impresses interviewers who’ve seen one too many burned-out loops.”