[LeetCode] 633. Sum of Square Numbers

https://leetcode.com/problems/sum-of-square-numbers/description/

leetcode - Sum of Square Numbers

문제 유형 : 수학, 투포인터

문제 난이도 : Medium

 

문제

Given a non-negative integer c, decide whether there're two integers a and b such that a2 + b2 = c.

 

음수가 아닌 정수 c가 주어진다. a^2+b^c = c를 만족하는 두 정수 a와 b가 있는지 확인하시오.

 

풀이

가장 기본적으로 떠올릴 수 있는 경우는 a = 0, b = c^(1/2)이다.

b가 c의 제곱근인 경우, 바로 true가 나온다.

 

아니라면, 

a*a+b*b를 sum이라 하자.

sum이 c보다 크면, b를 1 낮춰본다.

작으면, a를 1 키운다.

이를 a <= b인동안 시행하고, 그때까지 sum == c가 확인되지 않으면, false를 반환한다.

 

코드

C++

class Solution {
public:
    bool judgeSquareSum(int c) {
        long long a = 1, b = sqrt(c);

        if(b*b == c) return true;
        while(a <= b) {
            long long sum = a*a + b*b;
            if(sum == c) return true;
            else if(sum > c) {
                b--;
            } else {
                a++;
            }
        }

        return false;
    }
};