633. Sum of Square Numbers.md

633. Sum of Square Numbers

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

Example 1:

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

Example 2:

Input: c = 3
Output: false

Constraints:

• 0 <= c <= 2^31 - 1

---

Solution

This is a very simple implementational problem where we can iterate over one integer a and find whether b = c - a^2.

Approach

1. Iterate from i = 0 to sqrt(c).
2. calculate rem = c - i*i;
   • if rem is a square number, return true
3. if no solution, return false

Explanation with example

for c = 5,

a	rem	b	b^2 == rem
0	5	2	false
1	4	2	true

Complexity

• Time Complexity:

  • O(sqrt(c))

• Space Complexity:

  • O(1)

Code

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

Tags: C++, cpp, leetcode, leetcode 633, implementation