Leetcode 퍼즐 Sqrt (x)에 대한 내 솔루션의 문제점은 무엇입니까?

Question

저는 sqrt (x) (https://leetcode.com/problems/sqrtx/)라는 LeetCode 질문 번호 69를 작성 중입니다. 정수의 제곱근을 또 다른 정수로 반환하도록 요청했습니다. 아래 내 솔루션입니다.

public class Solution { 
    public int mySqrt(int x) { 
    int i = 0; 
    if(x==0) 
    { 
     return 0; 
    } 
    for(i = 1;i<x/2;i++) 
    { 
     if(((i*i)<=x)&&((i+1)*(i+1)>x)) 
     { 
      break; 
     } 
    } 

    return i; 
    } 
} 

코드를 제출하면 x> = 2147395600 인 모든 테스트 사례가 모두 실패합니다. x = 2147395600 일 때는 46340 대신 289398을 반환하는데 이는 올바른 대답입니다. 내 코드의 문제점은 무엇입니까?

Answer 1

내 코드를 시도 할 수 있습니다 :

이

public int mySqrt(int x) { 
     long i = 0; 
     long j = x; 
     int mid = 0; 
     if (x == 0) { 
      return 0; 
     } 
     if (x == 1) { 
      return 1; 
     } 
     while (i <= j) { 
      mid = (int)(i + j)/2; 
      if (x/mid == mid) { 
       return (int)mid; 
      } else if (x/mid > mid) { 
       i = mid + 1; 
      } else if (x/mid < mid) { 
       j = mid - 1; 
      } 
     } 
     return (int)j; 
     } 

Answer 2

대신 INT의 긴 사용합니다. 이것은 int가 2147395600까지만 올라 가기 때문이며, long은 그보다 훨씬 높습니다. 그러나 long으로 변환 한 다음 int로 변환해야한다는 비용이 발생합니다.