Leetcode: 69. Sqrt(x)

MySqrt Function in C++

Here is an implementation of the mySqrt() function in C++:

    class Solution {
    public:
        int mySqrt(int x) {
            if (x < 2) {
                return x; 
            } else {
                long int left = mySqrt(x >> 2) << 1;
                long int right = left + 1;
                return (right * right) > x ? left :  right;
            }
        }
    };
  

This code implements the square root function for a given input x. The mySqrt() function uses a binary search approach to find the square root of x in an efficient manner.

Complexity Analysis

The time complexity of this mySqrt() function is O(logN), where N is the value of x. This is because the function performs a binary search to find the square root, repeatedly dividing the range in half until the square root is found.

The space complexity of the function is O(1), as it uses only a constant amount of additional memory.

Example Usage

Here's an example of how you can use the mySqrt() function:

    Solution obj;
    int x = 16;
    int sqrtValue = obj.mySqrt(x);
    std::cout << "Square root of " << x << " is " << sqrtValue << std::endl;
  

The above code initializes an instance of the Solution class, sets the input value x to 16, and then calls the mySqrt() function to calculate the square root. The resulting square root value is then printed to the console.

Feel free to use this code and modify it as needed for your own projects.