Problem: Leet Code 69-Sqrt(x)

QUESTION:

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

You must not use any built-in exponent function or operator.

• For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.

Example 1:

Input: x = 4
Output: 2
Explanation: The square root of 4 is 2, so we return 2.

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since we round it down to the nearest integer, 2 is returned.

Constraints:

• 0 <= x <= 2<sup>31</sup> - 1

---

💭Analyzing question:

1. It’s clearly given that we are going to get a positive integer for which we must find the square root.

2. The condition is not to use any built-in function to derive the result, indirectly they mean that we need to solve this manually by optimising the approach.

3. Even if the number is not a perfect square, then we must truncate to lowest value of the decimal.

---

💡Approach:

• I started to think how do we calculate square root manually in mathematical way, then i noticed that when a number multiplied with itself twice, we call it square and vice versa results in square root logically.

• Initially I caught with an idea why don’t we use loop to start from 1 and end till that number as root will lie between that range only.

• But this will take more time as checking with each number, so decide to use Binary search algorithm to find the square root of that number similar to searching of an element (here searching square root of that number).

---

💻My Java Code:

My Brute force Approach

class Solution {
    public int mySqrt(int x) {
        if (x == 0 || x == 1) return x;

        int result = 0;

        // triyng every number from 1 to x
        for (int i = 1; i <= x; i++) {
            if ((long)i * i > x) { // using long to avoid overflow
                break;
            }
            result = i; // store the last i whose square <= x
        }

        return result;
    }
}

My Optimal Approach

class Solution {
    public int mySqrt(int x) {
        if(x==1 || x==0) return x;

        //Binary Search Algorithm

        int left = 1;
        int right = x;
        int ans = 0;

        while(left<=right){
            int mid = left+(right-left)/2;  //Finding middle element
            long square = (long) mid*mid;  //Storing square value in long to avoid overflow
            if(square == x){
    return mid;
            }
            else if(square < x){
                ans=mid;
                left=mid+1;
            }
            else{
                right=mid-1;
            } 
        }
        return ans;
    }
}

---

🖥️Output:

---

⏱️Efficiency of Approach:

Brute force Approach:

• Time Complexity: O(N) or O(√N)

• Space complexity: O(1)

Optimal Approach:

• Time Complexity: O(log N)

• Space complexity: O(1)

---

🧠My Learnings:

1. I understood that an algorithm like Binary Search is not used only for searching just any element, but the search indeed means searching elements based on our need

2. Binary Search Application and Finding Square root without using pre-defined functions.

---

Tags:

#Java #Leetcode #ProblemSolving #DSA