Problem Statement

Given a positive integer n. Find and return its square root. If n is not a perfect square, then return the floor value of sqrt(n).

Examples

Example 1:

Input: n = 36
Output: 6

Explanation: 6 is the square root of 36.

Example 2:

Input: n = 28
Output: 5

Explanation: The square root of 28 is approximately 5.292. So, the floor value will be 5.

Different Approaches

1️⃣ Brute Force Approach (Linear Search)

This approach incrementally checks each integer from 1 upwards, squaring it to see if it exceeds the input number. If it does, the algorithm returns the previous number.

Algorithm:

1. Start from 1.
2. Check if i * i exceeds n.
3. Stop when i * i > n, and return i - 1.

Dry Run:

Initialization:

n = 36

First Iteration:

i = 1
n = 36

Does i*i <= n
     1*1 <= 36
     1 <= 36
     True
     Increment i by 1.

Second Iteration:

i = 2
n = 36

Does i*i <= n
     2*2 <= 36
     4 <= 36
     True
     Increment i by 1.

Third Iteration:

i = 3
n = 36

Does i*i <= n
     3*3 <= 36
     19 <= 36
     True
     Increment i by 1.

Fourth Iteration:

i = 4
n = 36

Does i*i <= n
     4*4 <= 36
     16 <= 36
     True
     Increment i by 1.

Fifth Iteration:

i = 5
n = 36

Does i*i <= n
     5*5 <= 36
     25 <= 36
     True
     Increment i by 1.

Sixth Iteration:

i = 6
n = 36

Does i*i <= n
     6*6 <= 36
     36 <= 36
     True
     Increment i by 1.

Seventh Iteration:

i = 7
n = 36

Does i*i <= n
     7*7 <= 36
     49 <= 36
     False
     Break the loop

return i - 1, which is 6.

Code:

int squareRoot(int n) {
    int i = 1;
    while (i * i <= n) {
        i++;
    }
    return i - 1;
}

Complexity Analysis:

• Time Complexity: O(sqrt(n)), where n is the given number.
• Space Complexity: O(1)
  • As no additional space is used.

2️⃣ Optimal Approach (Binary Search)

Since the square root of a number is a non-decreasing function, we can use binary search to optimize the solution.

Steps:

1. Initialize low = 0 and high = x.
2. Calculate the middle value mid = low + (high - low) / 2.
3. If mid * mid == x, return mid.
4. If mid * mid < x, check in the right half by setting low = mid + 1.
5. If mid * mid > x, check in the left half by setting high = mid - 1.
6. The floor of the square root will be in high when the loop ends.

Dry Run:

Initialization:

n = 9
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
   
Left = 1
Right = 9

First Iteration:

n = 9

Left = 1
Right = 9
Mid = Left + (Right - Left) / 2
    = 1 + (9 - 1) / 2
    = 1 + 8/2
    = 5
MidSquare = 5 * 5
          = 25

+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
   ^                       ^                       ^
   |                       |                       |
  Left                    Mid                    Right

Check if SquareMid == n
         25 == 9
         False

Check if SquareMid < n
         25 < 9
         False
     Else
         // Go Left
         Right = mid - 1

Second  Iteration:

n = 9

Left = 1
Right = 4
Mid = Left + (Right - Left) / 2
    = 1 + (4 - 1) / 2
    = 1 + 3/2
    = 2
MidSquare = 2 * 2
          = 4

+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
   ^     ^           ^
   |     |           |
  Left  Mid        Right

Check if SquareMid == n
         4 == 9
         False

Check if SquareMid < n
         4 < 9
         True
         // Go Right
         Left = Mid + 1

Third Iteration:

n = 9

Left = 3
Right = 4
Mid = Left + (Right - Left) / 2
    = 3 + (4 - 3) / 2
    = 3 + 1/2
    = 3
MidSquare = 3 * 3
          = 9

+-----+-----+-----+-----+-----+-----+-----+-----+-----+
|  1  |  2  |  3  |  4  |  5  |  6  |  7  |  8  |  9  |
+-----+-----+-----+-----+-----+-----+-----+-----+-----+
               ^     ^
               |     |
              Left  Right
              Mid

Check if SquareMid == n
         9 == 9
         True

Return Mid which is 3.

Code:

#include <iostream>
using namespace std;

int squareRoot(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;
        int midSq = mid * mid;

        if (midSq == x) {
            return mid;  // Exact square root
        }

        if (midSq < x) {
            low = mid + 1;
            ans = mid;  // Update the floor value of the square root
        } else {
            high = mid - 1;
        }
    }

    return ans;  // Return the floor value
}

int main() {
    int x = 8;
    cout << "Square root of " << x << " is " << squareRoot(x) << endl;
    return 0;
}

Complexity Analysis:

• Time Complexity:O(log n) (The binary search reduces the search space by half in each step).
• Space Complexity:O(1) (No extra space required).