Square Root of an Integer
Description
Given a positive integer n, find the square root of n.
If n is a perfect square (e.g., 4, 9, 16, 25), return the exact square root.
If n is not a perfect square (e.g., 11, 20, 50), return the floor value of the square root — that is, the greatest integer whose square is less than or equal to n.
Floor value of a number is the largest integer that is less than or equal to that number. For example, floor(3.316) = 3.
Examples
Example 1
Input: n = 4
Output: 2
Explanation: 4 is a perfect square. 2 × 2 = 4, so the square root of 4 is exactly 2.
Example 2
Input: n = 11
Output: 3
Explanation: 11 is not a perfect square. 3 × 3 = 9 ≤ 11, but 4 × 4 = 16 > 11. Since the actual square root of 11 is approximately 3.316, the floor value is 3.
Example 3
Input: n = 1
Output: 1
Explanation: 1 is a perfect square. 1 × 1 = 1, so the square root is 1.
Example 4
Input: n = 25
Output: 5
Explanation: 25 is a perfect square. 5 × 5 = 25, so the square root is exactly 5.
Constraints
- 1 ≤ n ≤ 3 × 10^4
Editorial
Brute Force
Intuition
The most natural way to find the square root is to try every integer starting from 1. For each integer, we compute its square and check whether it exceeds n. The moment an integer's square exceeds n, the answer is the previous integer.
Think of it like guessing someone's age. You start from 1 and keep asking "Are you at least this old?" — incrementing each time. The moment the guess is too high, you know the answer is one less.
Specifically, we iterate i = 1, 2, 3, ... and check i * i ≤ n. The last value of i for which this holds true is our answer.
Step-by-Step Explanation
Let's trace through with n = 11:
Step 1: Start with i = 1. Compute 1 × 1 = 1. Is 1 ≤ 11? YES. Record answer = 1. Continue.
Step 2: i = 2. Compute 2 × 2 = 4. Is 4 ≤ 11? YES. Update answer = 2. Continue.
Step 3: i = 3. Compute 3 × 3 = 9. Is 9 ≤ 11? YES. Update answer = 3. Continue.
Step 4: i = 4. Compute 4 × 4 = 16. Is 16 ≤ 11? NO. 16 > 11. Stop immediately.
Step 5: Return the last valid answer = 3.
Result: floor(√11) = 3
Linear Search — Testing Each Integer's Square — We try i = 1, 2, 3, ... and compute i² until i² exceeds n. The last valid i is the floor square root.
Algorithm
- Initialize answer = 0 and i = 1.
- While i × i ≤ n:
a. Set answer = i (this is a valid candidate).
b. Increment i by 1. - Return answer.
Code
#include <iostream>
using namespace std;
class Solution {
public:
int floorSqrt(int n) {
int answer = 0;
for (int i = 1; i * i <= n; i++) {
answer = i;
}
return answer;
}
};class Solution:
def floorSqrt(self, n):
answer = 0
i = 1
while i * i <= n:
answer = i
i += 1
return answerclass Solution {
public int floorSqrt(int n) {
int answer = 0;
for (int i = 1; i * i <= n; i++) {
answer = i;
}
return answer;
}
}Complexity Analysis
Time Complexity: O(√n)
The loop runs from i = 1 until i × i > n. The maximum value of i is √n, so the loop executes √n iterations. For n = 30000, this means about 173 iterations — fast enough, but we can do better.
Space Complexity: O(1)
We use only two integer variables (answer, i). No additional data structures are needed.
Why This Approach Is Not Efficient
The linear scan checks every integer from 1 to √n one by one. While O(√n) is acceptable for the given constraints (n ≤ 3 × 10^4), the approach doesn't scale well for larger inputs. If n were up to 10^18 (a common constraint in competitive programming), √n would be 10^9 — far too many iterations.
The key observation is that perfect squares form a sorted sequence: 1, 4, 9, 16, 25, 36, 49, ... This is a monotonically increasing sequence. We're essentially searching for the position where i² ≤ n transitions to i² > n.
Whenever we search for a boundary in a sorted sequence, binary search is the optimal technique. Instead of checking every integer, we can check the middle of our search range and eliminate half the candidates at each step. This reduces the search from O(√n) to O(log n) — for n = 10^18, that's about 60 steps instead of 10^9.
Optimal Approach - Binary Search
Intuition
Since perfect squares form a sorted sequence (1, 4, 9, 16, 25, ...), we can use binary search to find the floor square root efficiently.
The search space is the range of integers from 1 to n. At each step, we pick the middle value mid and compute mid²:
- If
mid² == n, we've found an exact square root. Return mid. - If
mid² < n, then mid is a valid candidate for the floor square root (since mid² doesn't exceed n). But there might be a larger valid value, so we search the right half while recording mid as our best answer so far. - If
mid² > n, then mid is too large. The answer must be in the left half.
This is exactly the same pattern as finding the floor in a sorted array — we're looking for the largest integer whose square doesn't exceed n.
Imagine guessing a number between 1 and 100 where someone tells you "higher" or "lower" after each guess. Instead of trying 1, 2, 3, ... you'd start at 50, then go to 25 or 75, and so on. That's binary search — each guess eliminates half the remaining possibilities.
Step-by-Step Explanation
Let's trace through with n = 11:
Step 1: Initialize low = 1, high = 11, answer = 1.
Step 2: Compute mid = (1 + 11) / 2 = 6. Compute 6² = 36.
- Is 36 ≤ 11? NO. 36 > 11. The square root must be smaller.
- Set high = mid - 1 = 5.
Step 3: Compute mid = (1 + 5) / 2 = 3. Compute 3² = 9.
- Is 9 ≤ 11? YES. This is a valid candidate.
- Update answer = 3. Search right for potentially larger valid values.
- Set low = mid + 1 = 4.
Step 4: Compute mid = (4 + 5) / 2 = 4. Compute 4² = 16.
- Is 16 ≤ 11? NO. 16 > 11. Too large.
- Set high = mid - 1 = 3.
Step 5: low (4) > high (3). Loop ends.
Step 6: Return answer = 3.
Result: floor(√11) = 3. Found in just 3 comparisons!
Binary Search — Finding Floor Square Root of 11 — Watch how binary search halves the candidate range at each step, finding the largest integer whose square is ≤ n in logarithmic time.
Algorithm
- Initialize low = 1, high = n, answer = 1.
- While low ≤ high:
a. Compute mid = low + (high - low) / 2.
b. If mid × mid == n: exact square root found. Return mid.
c. If mid × mid < n: mid is a valid candidate. Set answer = mid and search right: low = mid + 1.
d. If mid × mid > n: mid is too large. Search left: high = mid - 1. - Return answer.
Code
#include <iostream>
using namespace std;
class Solution {
public:
int floorSqrt(int n) {
if (n == 0) return 0;
int low = 1, high = n;
int answer = 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if ((long long)mid * mid == n) {
return mid;
} else if ((long long)mid * mid < n) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
};class Solution:
def floorSqrt(self, n):
if n == 0:
return 0
low, high = 1, n
answer = 1
while low <= high:
mid = low + (high - low) // 2
if mid * mid == n:
return mid
elif mid * mid < n:
answer = mid
low = mid + 1
else:
high = mid - 1
return answerclass Solution {
public int floorSqrt(int n) {
if (n == 0) return 0;
int low = 1, high = n;
int answer = 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if ((long) mid * mid == n) {
return mid;
} else if ((long) mid * mid < n) {
answer = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return answer;
}
}Complexity Analysis
Time Complexity: O(log n)
At each step, binary search halves the search space. Starting with n candidates, after k steps we have n / 2^k candidates. The loop ends when n / 2^k < 1, giving k = log₂(n). For n = 3 × 10^4, this is about 15 comparisons. For n = 10^18, only about 60 comparisons — dramatically faster than the O(√n) brute force.
Space Complexity: O(1)
We use only three integer variables (low, high, answer). No additional data structures are needed. Space usage is constant regardless of input size.