633. Sum of Square Numbers

Posted on One min read

1. Description

Given a non-negative integer c, decide whether there’re two integers a and b such that $a^2$ + $b^2$ = c.

2. Example

Example 1

Input: c = 5
Output: true
Explanation: 1 * 1 + 2 * 2 = 5

Example 2

Input: c = 3
Output: false

3. Constraints

  • 0 <= c <= 2$^{31}$ - 1

4. Solutions

Library

n = c
Time complexity: O($\sqrt{n}$)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long i = 0, j = 0; i <= j; ++i) {
            j = sqrt(c - i * i);
            if (i * i + j * j == c) {
                return true;
            }
        }

        return false;
    }
};
Two Pointers

n = c
Time complexity: O($\sqrt{n}$)
Space complexity: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    bool judgeSquareSum(int c) {
        for (long left = 0, right = sqrt(c); left <= right;) {
            long multiply = left * left + right * right;
            if (multiply == c) {
                return true;
            }

            multiply < c ? ++left : --right;
        }

        return false;
    }
};
comments powered by Disqus