Square Root of a Number

55
0

Problem Statement

Given a non-negative integer N, find the square root of N.

If N is not a perfect square, return the floor value of its square root.

Example 1

Input: N = 36

Output: 6

Explanation: 6 x 6 = 36, so the square root of 36 is 6.

Example 2

Input: N = 28

Output: 5

Explanation: 5 x 5 = 25 and 6 x 6 = 36. Since 28 lies between 25 and 36, the floor square root is 5

Brute Force Approach

The integer square root of N is the largest integer whose square does not exceed N.

Starting from 1, check each number in increasing order. As long as i x i <= N, i is a possible answer. When i x i becomes greater than N, the previous number i - 1 is the required square root.

For N = 28:

1 x 1, 2 x 2, 3 x 3, 4 x 4, and 5 x 5 are at most 28.

6 x 6 is greater than 28, so the answer is 5.

Algorithm

  • Start with i = 1, the smallest possible positive integer square root.

  • Keep increasing i while i × i <= N, since i is still a valid candidate whose square does not exceed N.

  • Stop when i × i > N.

  • Return i - 1, which is the largest integer whose square is less than or equal to N.

Dry Run

Square Root Brute Dry Run

Square Root Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the floor square root by checking
possible values in increasing order.
*/
int floorSqrt(int n) {
int i = 1;
// Stop at the first value whose square exceeds n.
while (1LL * i * i <= n) {
i++;
}
return i - 1;
}
};
// Driver code starts
int main() {
int n = 28;
Solution solution;
cout << solution.floorSqrt(n) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(sqrt(N)), since every number from 1 to the square root of N is checked.

Space Complexity: O(1) because constant space is used.

Optimal Approach

The useful observation is that squares grow in a sorted way. For smaller numbers, the square is smaller. For larger numbers, the square is larger.

For N = 28:

1 x 1 = 1
2 x 2 = 4
3 x 3 = 9
4 x 4 = 16
5 x 5 = 25
6 x 6 = 36

Once the square becomes greater than N, every bigger number will also be too large. This gives a clean boundary. All valid answers are on the left side, and all too-large values are on the right side. Binary search is made exactly for this kind of boundary.

So instead of checking every number one by one, keep guessing the middle value.

  • If mid x mid <= N, then mid can be an answer, but a larger answer may still exist. Move right.

  • If mid x mid > N, then mid is too large. Move left.

The largest valid mid becomes the final answer.

Algorithm

  • Set low = 0, high = N, and ans = 0 as the smallest value possible for a square root is 0 and square root cannot be greater than N itself.

  • Find the middle value mid between low and high using mid = low + (high-low)/2 until low <= high(meaning search range is valid).

    • If mid x mid <= N, store mid as the current best answer because it is a valid square root candidate. Move low to mid + 1 to search for a bigger valid answer.

    • If mid x mid > n, move high to mid - 1 because the current value is too large and we search for a smaller value.

  • When the search ends, return ans.

Dry Run

Square Root Optimal Dry Run

Square Root Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the floor value of the square root of n
using binary search.
*/
int floorSqrt(int n) {
// ans stores the largest valid value found so far.
int ans = 0;
int low = 0;
int high = n;
while (low <= high) {
int mid = low + (high - low) / 2;
// Use long long so mid x mid does not overflow for large n.
long long square = 1LL * mid * mid;
// If mid x mid is valid, try to find a bigger valid value.
if (square <= n) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
return ans;
}
};
// Driver code starts
int main() {
int n = 28;
Solution sol;
cout << sol.floorSqrt(n) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(log N) because the search range is divided into half in every step that means binary search is done on N itself.

Space Complexity: O(1) because constant space is used.

Interview follow-up Questions

Yes, most standard libraries provide built-in square root functions: C++: std::sqrt() (from <cmath>) Java: Math.sqrt() Python: math.sqrt() JavaScript: Math.sqrt()

Two PointerBinary SearchTCS NQT

Read Similar Blogs

Comments0