Sqrtx

                                            
class Solution {
public:
    int mySqrt(int x) {
        if (x == 0 || x == 1) {
            return x;
        }
        
        long left = 1;
        long right = x;
        while (left < right) {
            long mid = left + (right - left) / 2;
            if (mid * mid == x) {
                return mid;
            } else if (mid * mid < x) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left - 1;
    }
};

                                            
class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        long left = 1, right = x;
        while (left < right) {
            long mid = left + (right - left + 1) / 2;
            if (mid * mid > x) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        return (int)left;
    }
}

                                            
class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x == 0:
            return 0
        
        left, right = 1, x
        while left <= right:
            mid = (left + right) // 2
            if mid * mid <= x < (mid + 1) * (mid + 1):
                return mid
            elif x < mid * mid:
                right = mid
            else:
                left = mid + 1

                                            
int mySqrt(int x) {
    if (x == 0) {
        return 0;
    }
    
    long left = 1;
    long right = x;
    long ans = 0;

    while (left <= right) {
        long mid = left + (right - left) / 2;
        long square = mid * mid;
        
        if (square == x) {
            return mid;
        } else if (square < x) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return ans;
}

                                            
/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    if (x < 2) {
        return x;
    }
    
    let left = 1;
    let right = x;
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        
        if (mid * mid === x) {
            return mid;
        } else if (mid * mid < x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return right - 1;
};

                                            
class Solution {
    /**
     * @param Integer $x
     *
     * @return Integer
     */
    function mySqrt($x) {
        $left = 0;
        $right = $x;
        
        while ($left <= $right) {
            $mid = $left + intval(($right - $left) / 2);
            if ($mid * $mid == $x) {
                return $mid;
            } elseif ($mid * $mid < $x) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }
        
        return $right;
    }
}

                                            
class Solution {
    func mySqrt(_ x: Int) -> Int {
        if x == 0 {
            return 0
        }
        
        var left = 1
        var right = x
        
        while left < right {
            let mid = left + (right - left + 1) / 2
            if mid * mid > x {
                right = mid - 1
            } else {
                left = mid
            }
        }
        
        return left
    }
}

                                            
class Solution {
    fun mySqrt(x: Int): Int {
        if (x == 0) return 0
        var left = 1
        var right = x
        while (left < right) {
            val mid = left + (right - left) / 2
            if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
                return mid
            } else if (mid > x / mid) {
                right = mid
            } else {
                left = mid + 1
            }
        }
        return left
    }
}

                                            
class Solution {
  int mySqrt(int x) {
    if (x == 0) return 0;
    
    int left = 1;
    int right = x;
    int result = 0;
    
    while (left <= right) {
      int mid = left + ((right - left) ~/ 2);
      if (mid <= x ~/ mid) {
        result = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    return result;
  }
}

                                            
func mySqrt(x int) int {
    if x == 0 {
        return 0
    }
    
    left, right := 1, x
    for left <= right {
        mid := left + (right - left) / 2
        if mid == x / mid {
            return mid
        } else if mid < x / mid {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return right
}

                                            
# @param {Integer} x
# @return {Integer}
def my_sqrt(x)
    return Math.sqrt(x).to_i
end

                                            
object Solution {
    def mySqrt(x: Int): Int = {
        if (x == 0) return 0
        var left = 1
        var right = x
        while (left <= right) {
            val mid = left + (right - left) / 2
            if (mid * mid == x) return mid
            else if (mid * mid < x) left = mid + 1
            else right = mid - 1
        }
        right
    }
}

                                            
impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x == 0 {
            return 0;
        }
        
        let mut left = 1;
        let mut right = x;
        
        while left < right {
            let mid = left + (right - left) / 2;
            if mid > x / mid {
                right = mid;
            } else {
                if mid + 1 > x / (mid + 1) {
                    return mid;
                }
                left = mid + 1;
            }
        }
        
        return left;
    }
}

                                            
defmodule Solution do
  @spec my_sqrt(x :: integer) :: integer
  def my_sqrt(x) do
    if x == 0, do: 0, else: :math.sqrt(x) |> trunc
  end
end

To solve this coding challenge, we need to implement a function that computes the square root of a given non-negative integer \(x\), rounded down to the nearest integer. The challenge specifies that we must not use any built-in exponent function or operator.

Explanation

We can approach this problem using the binary search algorithm. Binary search is effective here because it allows us to narrow down the potential square root quickly by halving the search space in each step. The essential idea is to find the largest integer \(m\) such that: \[ m^2 \leq x \] We will use a loop to repeatedly halve our search space based on the value of \( m^2 \) compared to \( x \). Here's the detailed step-by-step explanation of the algorithm:

Initial Check: If \( x = 0 \), then the square root is 0.
Binary Search Setup: We initialize two pointers,
left

and
right

, to represent the search space.
left

starts at 1, and
right

starts at \( x \).
Binary Search Loop:

Calculate
mid

as the average of
left

and
right

.
Check if
mid * mid

equals \( x \).
If
mid * mid

is equal to \( x \), return
mid

since we found the exact square root.
If `mid mid` is less than \( x \) but \( (mid + 1) (mid + 1) \) is greater than \( x \), return
mid

as it means \( mid \) is the largest integer where \( mid^2 \leq x \).
Adjust the search range based on the comparison:

If
mid * mid

is greater than \( x \), move
right

to
mid - 1

.
If
mid * mid

is less than \( x \), move
left

to
mid + 1

.

Return Result: The loop continues until we narrow down the potential values, and we return the appropriate integer value.

Below is the pseudocode implementing this logic:

                                            
# Function to find the square root of x, rounded down to the nearest integer
function mySqrt(x):
# Handle the edge case where x is 0
if x == 0:
return 0

# Initialize the binary search range
left = 1
right = x

# Perform binary search
while left <= right:
# Calculate the middle point
mid = (left + right) // 2

# Check if mid^2 is less than or equal to x and (mid+1)^2 is greater than x
if mid * mid <= x and (mid + 1) * (mid + 1) > x:
return mid
# If mid^2 is greater than x, adjust the right pointer
elif mid * mid > x:
right = mid - 1
# If mid^2 is less than x, adjust the left pointer
else:
left = mid + 1

# Return the result; the loop ensures we find the correct integer
return mid

Step-by-Step Explanation

Function Entry: We call
mySqrt(x)

, where \(x\) is the integer for which we want to find the square root.

If \(x\) is 0, return 0 immediately, because the square root of 0 is 0.
Initialize
left

to 1 and
right

to
x

.

Binary Search Loop:

Calculate
mid

as the integer division of
(left + right) // 2

.
Check if `mid mid
is less than or equal to

x
, but

(mid + 1) (mid + 1)` is greater than `x`:

If true, return
mid

because
mid

is the largest integer whose square is less than or equal to
x

.

If
mid * mid

is greater than
x

, adjust the search range by setting
right

to
mid - 1

.
If
mid * mid

is less than
x

, adjust the search range by setting
left

to
mid + 1

.

Conclusion: The loop iteratively narrows down the search space until we find the largest integer where its square is less than or equal to
x

. Return this integer.

By following these steps, we obtain an efficient solution to calculate the square root of a non-negative integer, rounded down to the nearest integer, without using built-in exponent functions.