Find square root of a number

Intuition:

The idea here is to search for the floor of the square root of the given number linearly. For each number from 1 to the given number, find its square and check if it is smaller than the given number, if it is, store the current integer as potential root, else break out of the loop as the further calculations will only provide larger square roots.

Approach:

Start with ans initialized to 0, which will eventually hold the floor of the square root of n.
Iterate using a for loop, ranging from 1 to n. For each integer compute 'val' as the square of the current integer.
Check if 'val' is less than or equal to n. If true update 'ans' to the current value of the integer, because the current integer is a candidate for the square root.
If val exceeds n, break out of the loop since further values of the next integer will only yield larger squares.
Once the loop completes, ans contains the largest integer such that ans * ans is less than or equal to n, providing the floor of the square root of n. Finally return ans.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to compute the floor of square root
       of a given integer */
    long long floorSqrt(long long n) {
        long long ans = 0;
        
        // Linear search in the answer space
        for (long long i = 1; i <= n; i++) {
            long long val = i * i;
            // Check if val is less than or equal to n
            if (val <= n * 1ll) {
                ans = i; // Update ans to current value of i
            } else {
                break; // Exit loop if val exceeds n
            }
        }
        
        // Return the computed floor of square root
        return ans;
    }
};

int main() {
    int n = 28;
    
    // Create an object of the Solution class
    Solution sol;
    
    int ans = sol.floorSqrt(n);
    
    // Print the result
    cout << "The floor of square root of " << n
         << " is: " << ans << "\n";
    
    return 0;
}
class Solution {
    /* Function to compute the floor of
       square root of a given integer */
    public long floorSqrt(long n) {
        long ans = 0;
        
        // Linear search in the answer space
        for (long i = 1; i <= n; i++) {
            long val = i * i;
            
            // Check if val is less than or equal to n
            if (val <= (long) n) {
                // Update ans to current value of i
                ans = (int) i; 
            } 
            else {
                break; 
            }
        }
        
        // Return the computed floor of square root
        return ans;
    }
    
    public static void main(String[] args) {
        int n = 28;
        
        // Create an object of the Solution class
        Solution sol = new Solution();
        
        int ans = sol.floorSqrt(n);
        
        // Print the result
        System.out.println("The floor of square root of " + n
                           + " is: " + ans);
    }
}
class Solution:
    """ Function to compute the floor of
        square root of a given integer """
    def floorSqrt(self, n: int) -> int:
        ans = 0
        
        # Linear search in the answer space
        for i in range(1, n + 1):
            val = i * i
            
            # Check if val is less than or equal to n
            if val <= n:
                # Update ans to current value of i
                ans = i
            else:
                break
        
        # Return the computed floor of square root
        return ans

if __name__ == "__main__":
    n = 28
    
    # Create an object of the Solution class
    sol = Solution()
    
    ans = sol.floorSqrt(n)
    
    # Print the result
    print(f"The floor of square root of {n} is: {ans}")
class Solution {
    /* Function to compute the floor of
       square root of a given integer */
    floorSqrt(n) {
        let ans = 0;
        
        // Linear search in the answer space
        for (let i = 1; i <= n; i++) {
            let val = i * i;
            
            // Check if val is less than or equal to n
            if (val <= n) {
                // Update ans to current value of i
                ans = i; 
            } 
            else {
                break; 
            }
        }
        
        // Return the computed floor of square root
        return ans;
    }
}

// Main function to test the floorSqrt method
let n = 28;

// Create an object of the Solution class
let sol = new Solution();

let ans = sol.floorSqrt(n); 


// Print the result
console.log(`The floor of square root of ${n} is: ${ans}`);

Complexity Analysis:

Time Complexity:O(N^1/2), where N is the given number. Since we are using linear search, and the loop iterates up to sqrt(N) before breaking out.

Space Complexity: As no additional space is used, so the Space Complexity is O(1).

Intuition:

Binary Search algorithm can be used to optimize the brute force solution. While applying the binary search algorithm, compare the square of mid with the given number, if the square is less than or equal to the given number, store the mid as it can be a potential root and eliminate the left half of the search space, else eliminate the right half.

Approach:

Start with initializing low to 1 and high initialized to n, where n is the given number, defining the search range for ans. Also, initialize ans to 0 to store the answer.
Use a while loop, where it continues to search until low exceeds high. Calculate 'mid' as the midpoint between low and high. Compute val as mid * mid, the square of the midpoint.
Check if 'val' is less than or equal to n, if true, it means mid could be a potential candidate for the square root. Store the mid in 'ans' and move the search to the right part by updating low to mid + 1. If false, move the search to the left part by updating high to mid - 1 because mid is too high and mid * mid exceeds n
Once the while loop exits, 'ans' holds the largest integer ans such that ans * ans does not exceed n.

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    /* Function to compute the floor of
       square root of a given integer */
    long long floorSqrt(long long n) {
        long long low = 1, high = n;
        
        // Binary search on the answer space
        while (low <= high) {
            long long mid = (low + high) / 2;
            long long val = mid * mid;
            
            // Check if val is less than or equal to n
            if (val <= (long long)(n)) {
                // Move to the right part
                low = mid + 1;
            } else {
                // Move to the left part
                high = mid - 1;
            }
        }
        
        // Return the floor of square root
        return high;
    }
};

int main() {
    int n = 28;
    
    // Create an object of the Solution class
    Solution sol;
    
    int ans = sol.floorSqrt(n);
    
    // Print the result
    cout << "The floor of square root of " << n
         << " is: " << ans << "\n";
    
    return 0;
}
class Solution {
    /* Function to compute the floor of
       square root of a given integer */
    public long floorSqrt(long n) {
        long low = 1, high = n;
        
        // Binary search on the answer space
        while (low <= high) {
            long mid = (long)(low + high) / 2;
            long val = mid * mid;
            
            // Check if val is less than or equal to n
            if (val <= (long)(n)) {
                // Move to the right part
                low = (int)(mid + 1);
            } else {
                // Move to the left part
                high = (int)(mid - 1);
            }
        }
        
        // Return the floor of square root
        return high;
    }

    public static void main(String[] args) {
        int n = 28;
        
        // Create an object of the Solution class
        Solution sol = new Solution();
        
        int ans = sol.floorSqrt(n);
        
        // Print the result
        System.out.println("The floor of square root of " + n + " is: " + ans);
    }
}
class Solution:
    """ Function to compute the floor of
        square root of a given integer """
    def floorSqrt(self, n: int) -> int:
        low, high = 1, n
        
        # Binary search on the answer space
        while low <= high:
            mid = (low + high) // 2
            val = mid * mid
            
            # Check if val is less than or equal to n
            if val <= n:
                # Move to the right part
                low = mid + 1
            else:
                # Move to the left part
                high = mid - 1
        
        # Return the floor of square root
        return high

if __name__ == "__main__":
    n = 28
    
    # Create an object of the Solution class
    sol = Solution()
    
    ans = sol.floorSqrt(n)
    
    # Print the result
    print(f"The floor of square root of {n} is: {ans}")
class Solution {
    /* Function to compute the floor of
       square root of a given integer */
    floorSqrt(n) {
        let low = 1, high = n;
        
        // Binary search on the answer space
        while (low <= high) {
            let mid = Math.floor((low + high) / 2);
            let val = mid * mid;
            
            // Check if val is less than or equal to n
            if (val <= n) {
                // Move to the right part
                low = mid + 1;
            } else {
                // Move to the left part
                high = mid - 1;
            }
        }
        
        // Return the floor of square root
        return high;
    }
}

// Main function to test the solution
let n = 28;

// Create an object of the Solution class
let sol = new Solution();

let ans = sol.floorSqrt(n);

// Print the result
console.log(`The floor of square root of ${n} is: ${ans}`);

Complexity Analysis:

Time Complexity:O(logN), where N is the given number. We are basically using the Binary Search algorithm.

Space Complexity: As no additional space is used, so the Space Complexity is O(1).

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Complexity Analysis:

Intuition:

Approach:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code