Is Sum of Square Numbers easy or hard?

The problem is rated Medium because the brute force idea is straightforward but recognizing the two‑pointer optimization requires pattern recognition. Candidates who connect it to the two‑sum technique on a sorted range typically reach the optimal solution quickly.

Sum of Square Numbers Python/Java solution

Most solutions compute values up to sqrt(c). In Python or Java, initialize two pointers at 0 and sqrt(c), calculate a² + b², and adjust the pointers until the sum equals c or the pointers cross. This implementation runs in O(sqrt(c)) time with O(1) space.

How to solve Sum of Square Numbers in O(n)?

Instead of checking all pairs, restrict values to the square root range. Use two pointers: one starting at 0 and the other at floor(sqrt(c)). Compute a² + b² and move the pointers accordingly. This reduces the search to O(sqrt(c)) operations with constant memory.

What is the best approach for Sum of Square Numbers?

The two pointers approach is typically the best solution. Start with left = 0 and right = floor(sqrt(c)), then adjust the pointers based on whether a² + b² is smaller or larger than c. This runs in O(sqrt(c)) time and O(1) space while avoiding nested loops.

Is Sum of Square Numbers asked at Google/Amazon/Meta?

Sum of Square Numbers appears in interviews that test number theory and pointer techniques. Variations of the problem have been reported in interviews at companies like Google, Amazon, and Meta because it evaluates mathematical reasoning and efficient search patterns.

What data structure is used in Sum of Square Numbers?

No special data structure is required. The optimal approach relies on the two pointers technique over a numeric range, combined with basic math operations on squares and square roots.

What is the time complexity of Sum of Square Numbers?

The optimal solution runs in O(sqrt(c)) time because the search space for values of a and b only goes up to the square root of c. Both the mathematical brute force method and the two‑pointer method achieve this complexity with constant O(1) space.

Description Solution Video 14:26

633. Sum of Square Numbers

Medium37.0% acceptance6 companies

Given a non-negative integer c, decide whether there're two integers a and b such that a² + b² = 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³¹ - 1

Asked at 6 companies

LinkedIn Bloomberg

Google Amazon Meta Microsoft

Topics

14:26

Still stuck?Read 4 approaches, or watch a walkthrough.

Open solution

633. Sum of Square Numbers

Asked at 6 companies

Topics

Similar problems