LeetCode 633. Sum of Square Numbers

Description

Given a non-negative integer

c

, your task is to decide whether there’re two integers

a

and

b

such that a2+b2=c .

Example 1:

Input: 5

Output: True

Explanation:1 * 1 + 2 * 2 = 5

Example 2:

Input: 3

Output: False

Analysis

這道題不需要很複雜的數論知識，純暴力也可以過，但兩層循環周遊可能的數字會TLE，要利用

a

,

b

兩數之間的關系，一層循環即可，直接利用sqrt()函數和強制類型轉換即可AC。

Code

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long a = ; a * a <= c; a++){
            double b = sqrt(c - a * a);
            if ((int)b == b)
                return true;            
        }
        return false;
    }
};
           

Appendix

• Link: https://leetcode.com/problems/sum-of-square-numbers/
• Run Time: 13ms