ProblemPermalink

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

• 0 <= x <= 2^31 - 1

SolutionPermalink

LogicPermalink

1. 제곱근 root를 0부터 시작해 1씩 늘려가면서 제곱근 root의 제곱을 구하고, 해당 제곱이 정수 x를 초과하는 시점에 root - 1을 반환한다.

2. 제곱근 root를 제곱이 정수형의 최대 범위인 2^31 - 1를 벗어나면 제곱근 root가 가질 수 있는 값 중 가장 큰 값을 가진 것이므로 즉시 root - 1을 반환한다.

   CodePermalink

   class Solution {
    public int mySqrt(int x) {
        int root = 0;
        int prev = 0;
        while (root * root <= x) {
            if (root * root < prev) break;
            prev = root * root;
            root++;
        } return root - 1;
    }
   }
   

   Time ComplexityPermalink

   • 정수 x의 크기를 n이라 가정했을 때, 아래 반복문은 O(sqrt(n))의 시간 복잡도를 가진다. 따라서 본 문제는 O(sqrt(n))의 시간 복잡도를 가진다.

     int root = 0;
     int prev = 0;
     while (root * root <= x) {
      if (root * root < prev) break;
      prev = root * root;
      root++;
     }