Sum of Square Numbers

Sum of Square Numbers

What is this problem about?

The "Sum of Square Numbers interview question" is a popular mathematical coding problem. You are given a non-negative integer c, and your task is to determine whether there exist two integers a and b such that a^2 + b^2 = c. This is a direct application of number theory and search algorithms.

While the problem sounds simple, it appears frequently in interviews at Apple, Google, and Microsoft because it can be solved in multiple ways, each with different time and space complexities. It is a great way to see how a candidate optimizes a solution from O(c) down to O(sqrt(c)).

Why is this asked in interviews?

This "Sum of Square Numbers coding problem" is asked to test:

1. Mathematical Intuition: Understanding that a and b cannot exceed sqrt(c).
2. Search Optimization: Can you find the pair without checking every single combination?
3. Two-Pointer Technique: Efficiently narrowing down a search range.
4. Edge Case Handling: Dealing with zero, perfect squares, and large integers.

Algorithmic pattern used

The most efficient "Math interview pattern" for this problem is the Two-Pointers approach. Since we know a^2 + b^2 = c, both a and b must be in the range [0, sqrt(c)].

• Set left = 0 and right = floor(sqrt(c)).
• Calculate sum = left*left + right*right.
• If sum == c, return true.
• If sum < c, increment left to increase the sum.
• If sum > c, decrement right to decrease the sum. Alternatively, a "Binary Search interview pattern" can be used where for each a, you binary search for b^2 = c - a^2.

Example explanation

Let c = 5.

1. Range is [0, sqrt(5)] which is [0, 1, 2].
2. Start with left = 0, right = 2.
3. 0^2 + 2^2 = 0 + 4 = 4.
4. 4 < 5, so increment left. left = 1.
5. 1^2 + 2^2 = 1 + 4 = 5.
6. 5 == 5, return true.

If c = 3:

1. Range is [0, 1].
2. 0^2 + 1^2 = 1 (too small).
3. Increment left to 1. 1^2 + 1^2 = 2 (too small).
4. No more moves possible, return false.

Common mistakes candidates make

• Checking up to c: A common novice mistake is running a loop up to c or c/2, which results in O(c) complexity and will time out for large values like 2^31 - 1.
• Integer Overflow: Calculating a*a + b*b can exceed the range of a 32-bit integer before comparing it to c. Using 64-bit integers (long) is necessary.
• Missing 0: Forgetting that a or b can be zero (e.g., if c=4, 0^2 + 2^2 = 4).

Interview preparation tip

Always start by identifying the bounds of your search. In "Math coding patterns", if you are looking for squares, the square root of the target is almost always your upper bound. This immediately reduces your search space from millions to thousands. Also, remember the Fermat's Theorem on Sum of Two Squares as a fun fact: a number can be expressed as a sum of two squares if and only if its prime factors of the form 4k + 3 occur with an even exponent.