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
iwhilei×i <= N, sinceiis still a valid candidate whose square does not exceedN.Stop when
i×i > N.Return
i - 1, which is the largest integer whose square is less than or equal toN.
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 startsint 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 = 12 x 2 = 43 x 3 = 94 x 4 = 165 x 5 = 256 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, thenmidcan be an answer, but a larger answer may still exist. Move right.If
mid x mid > N, thenmidis too large. Move left.
The largest valid mid becomes the final answer.
Algorithm
Set
low = 0,high = N, andans = 0as the smallest value possible for a square root is 0 and square root cannot be greater than N itself.Find the middle value
midbetweenlowandhighusingmid = low + (high-low)/2until low <= high(meaning search range is valid).If
mid x mid <= N, storemidas the current best answer because it is a valid square root candidate. Movelowtomid + 1to search for a bigger valid answer.If
mid x mid > n, movehightomid - 1because 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
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 startsint 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()
Be the first to add a comment.