144. Two Squares Make It
A tile designer has exactly c unit cells to cover and owns two square rugs. Each rug has a whole-number side length, and a rug may have side 0, which means it is left unused. Both rugs together must cover exactly c cells, no more and no less.
Given a non-negative integer c, return true if there are non-negative integers a and b with a*a + b*b == c, otherwise return false. The two sides may be equal. Because c can be as large as 2^31 - 1, trying every pair of sides is far too slow; aim for about the square root of c steps.
Example 1
- Input:
- c = 13
- Output:
- true
- Explanation:
13 = 2*2 + 3*3 = 4 + 9, so the answer is true.
Example 2
- Input:
- c = 14
- Output:
- false
- Explanation:
The squares up to 14 are 0, 1, 4, 9. No two of them add up to 14, so the answer is false.
Example 3
- Input:
- c = 8
- Output:
- true
- Explanation:
Both rugs may have the same side: 2*2 + 2*2 = 8, so the answer is true.
Constraints
0 ≤ c ≤ 231 - 1
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(sqrt(c))
- Space
- O(1)