633. Sum of Square Numbers - Solution

The problem

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

Approach overview

Problem Overview: Given a non‑negative integer c, determine whether there exist integers a and b such that a² + b² = c. The task is essentially checking whether the number can be represented as the sum of two perfect squares.

Approach 1: Mathematical Interpretation and Brute Force (O(√c) time, O(1) space)

The direct way is to iterate one value and check whether the remaining value forms a perfect square. Loop a from 0 to sqrt(c). For each value, compute b² = c - a² and check if b² is a perfect square using sqrt() or an integer check. If b * b == b², the equation holds and the answer is true. This works because a cannot exceed √c, which limits the search space significantly. The approach relies heavily on math reasoning about perfect squares and avoids checking every pair of numbers.

Approach 2: Two Pointers (O(√c) time, O(1) space)

This method treats the possible square values like a sorted range and applies the classic two pointers pattern. Initialize left = 0 and right = floor(sqrt(c)). Compute sum = left² + right². If the sum equals c, a valid pair exists. If the sum is smaller, increment left to increase the value. If the sum is larger, decrement right to reduce it. Because squares grow monotonically, this pointer movement systematically explores all combinations without nested loops. The technique mirrors the two‑sum pattern on a sorted array of square values.

Some implementations replace the perfect square check with a binary search on b, but that increases the time complexity to O(√c log c). The two‑pointer approach achieves the same goal with fewer operations and simpler logic.

Recommended for interviews: Start with the mathematical brute force idea to show you recognize the constraint a ≤ √c. Then move to the two‑pointer approach. Interviewers typically expect this optimization because it demonstrates pattern recognition and efficient search on a monotonic range while maintaining constant space.

Approach 1: Using Two Pointers

The first approach involves using the two-pointer technique. Given an integer c, you start with two pointers a initialized at 0 and b initialized at the square root of c. You calculate a^2 + b^2 and compare it with c. If it equals c, return true. If the sum is less than c, increment a to increase the sum. If the sum is greater than c, decrement b to decrease the sum. Continue this until a exceeds b.

Python

import math

def judgeSquareSum(c):
    a = 0
    b = int(math.sqrt(c))
    while a <= b:
        sum = a * a + b * b
        if sum == c:
            return True
        elif sum < c:
            a += 1
        else:
            b -= 1
    return False

Java

import java.lang.Math;

public class Solution {
    public boolean judgeSquareSum(int c) {
        int a = 0;
        int b = (int) Math.sqrt(c);
        while (a <= b) {
            int sum = a * a + b * b;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                a++;
            } else {
                b--;
            }
        }
        return false;
    }
}

C++

#include <cmath>
#include <iostream>

bool judgeSquareSum(int c) {
    int a = 0;
    int b = static_cast<int>(std::sqrt(c));
    while (a <= b) {
        int sum = a * a + b * b;
        if (sum == c) {
            return true;
        } else if (sum < c) {
            a++;
        } else {
            b--;
        }
    }
    return false;
}

JavaScript

function judgeSquareSum(c) {
    let a = 0;
    let b = Math.floor(Math.sqrt(c));
    while (a <= b) {
        const sum = a * a + b * b;
        if (sum === c) {
            return true;
        } else if (sum < c) {
            a++;
        } else {
            b--;
        }
    }
    return false;
}

#include <stdbool.h>
#include <math.h>

bool judgeSquareSum(int c) {
    int a = 0;
    int b = (int)sqrt(c);
    while (a <= b) {
        int sum = a * a + b * b;
        if (sum == c) {
            return true;
        } else if (sum < c) {
            a++;
        } else {
            b--;
        }
    }
    return false;
}

using System;

public class Solution {
    public bool JudgeSquareSum(int c) {
        int a = 0;
        int b = (int)Math.Sqrt(c);
        while (a <= b) {
            int sum = a * a + b * b;
            if (sum == c) {
                return true;
            } else if (sum < c) {
                a++;
            } else {
                b--;
            }
        }
        return false;
    }
}

Python's implementation uses math.sqrt and an iterative check using the two-pointer technique.

Complexity

Time Complexity: O(sqrt(c))
Space Complexity: O(1)

Try this approach in the editor

Approach 2: Mathematical Interpretation and Brute Force

This approach is a brute-force method. Start with a single loop iterating from a = 0 to sqrt(c). For each value of a, calculate a^2 and check if c - a^2 is a perfect square. If it is, return true, otherwise continue. If the loop completes without finding such values, return false.

Python

import math

def isPerfectSquare(num):
    sq = int(math.sqrt(num))
    return sq * sq == num

def judgeSquareSum(c):
    for a in range(int(math.sqrt(c)) + 1):
        if isPerfectSquare(c - a * a):
            return True
    return False

Java

class Solution {
    private boolean isPerfectSquare(int num) {
        int sq = (int) Math.sqrt(num);
        return sq * sq == num;
    }

    public boolean judgeSquareSum(int c) {
        for (int a = 0; a * a <= c; a++) {
            if (isPerfectSquare(c - a * a)) {
                return true;
            }
        }
        return false;
    }
}

C++

#include <cmath>

bool isPerfectSquare(int num) {
    int sq = static_cast<int>(std::sqrt(num));
    return sq * sq == num;
}

bool judgeSquareSum(int c) {
    for (int a = 0; a * a <= c; a++) {
        if (isPerfectSquare(c - a * a)) {
            return true;
        }
    }
    return false;
}

JavaScript

function isPerfectSquare(num) {
    const sq = Math.floor(Math.sqrt(num));
    return sq * sq === num;
}

function judgeSquareSum(c) {
    for (let a = 0; a * a <= c; a++) {
        if (isPerfectSquare(c - a * a)) {
            return true;
        }
    }
    return false;
}

#include <stdbool.h>
#include <math.h>

bool isPerfectSquare(int num) {
    int sq = (int)sqrt(num);
    return sq * sq == num;
}

bool judgeSquareSum(int c) {
    for (int a = 0; a * a <= c; a++) {
        if (isPerfectSquare(c - a * a)) {
            return true;
        }
    }
    return false;
}

using System;

public class Solution {
    private bool IsPerfectSquare(int num) {
        int sq = (int)Math.Sqrt(num);
        return sq * sq == num;
    }

    public bool JudgeSquareSum(int c) {
        for (int a = 0; a * a <= c; a++) {
            if (IsPerfectSquare(c - a * a)) {
                return true;
            }
        }
        return false;
    }
}

In Python, the function isPerfectSquare is used to determine if c - a^2 is a perfect square by checking for each a.

Complexity

Time Complexity: O(sqrt(c) * log(c))
Space Complexity: O(1)

Try this approach in the editor

Approach 3: Mathematics + Two Pointers

We can use the two-pointer method to solve this problem. Define two pointers a and b, pointing to 0 and \sqrt{c} respectively. In each step, we calculate the value of s = a^2 + b^2, and then compare the size of s and c. If s = c, we have found two integers a and b such that a^2 + b^2 = c. If s < c, we increase the value of a by 1. If s > c, we decrease the value of b by 1. We continue this process until we find the answer, or the value of a is greater than the value of b, and return false.

The time complexity is O(\sqrt{c}), where c is the given non-negative integer. The space complexity is O(1).

TypeScript

function judgeSquareSum(c: number): boolean {
    let [a, b] = [0, Math.floor(Math.sqrt(c))];
    while (a <= b) {
        const s = a * a + b * b;
        if (s === c) {
            return true;
        }
        if (s < c) {
            ++a;
        } else {
            --b;
        }
    }
    return false;
}

func judgeSquareSum(c int) bool {
	a, b := 0, int(math.Sqrt(float64(c)))
	for a <= b {
		s := a*a + b*b
		if s == c {
			return true
		}
		if s < c {
			a++
		} else {
			b--
		}
	}
	return false
}

Rust

use std::cmp::Ordering;

impl Solution {
    pub fn judge_square_sum(c: i32) -> bool {
        let mut a: i64 = 0;
        let mut b: i64 = (c as f64).sqrt() as i64;
        while a <= b {
            let s = a * a + b * b;
            match s.cmp(&(c as i64)) {
                Ordering::Equal => {
                    return true;
                }
                Ordering::Less => {
                    a += 1;
                }
                Ordering::Greater => {
                    b -= 1;
                }
            }
        }
        false
    }
}

Try this approach in the editor

Approach 4: Mathematics

This problem is essentially about the conditions under which a number can be expressed as the sum of two squares. This theorem dates back to Fermat and Euler and is a classic result in number theory.

Specifically, the theorem can be stated as follows:

A positive integer n can be expressed as the sum of two squares if and only if all prime factors of n of the form 4k + 3 have even powers.

This means that if we decompose n into the product of its prime factors, n = p_1^{e_1} p_2^{e_2} cdots p_k^{e_k}, where p_i are primes and e_i are their corresponding exponents, then n can be expressed as the sum of two squares if and only if all prime factors p_i of the form 4k + 3 have even exponents e_i.

More formally, if p_i is a prime of the form 4k + 3, then for each such p_i, e_i must be even.

For example:

The number 13 is a prime and 13 \equiv 1 \pmod{4}, so it can be expressed as the sum of two squares, i.e., 13 = 2^2 + 3^2.
The number 21 can be decomposed into 3 times 7, where both 3 and 7 are prime factors of the form 4k + 3 and their exponents are 1 (odd), so 21 cannot be expressed as the sum of two squares.

In summary, this theorem is very important in number theory for determining whether a number can be expressed as the sum of two squares.

The time complexity is O(\sqrt{c}), where c is the given non-negative integer. The space complexity is O(1).

TypeScript

function judgeSquareSum(c: number): boolean {
    const n = Math.floor(Math.sqrt(c));
    for (let i = 2; i <= n; ++i) {
        if (c % i === 0) {
            let exp = 0;
            while (c % i === 0) {
                c /= i;
                ++exp;
            }
            if (i % 4 === 3 && exp % 2 !== 0) {
                return false;
            }
        }
    }
    return c % 4 !== 3;
}

func judgeSquareSum(c int) bool {
	n := int(math.Sqrt(float64(c)))
	for i := 2; i <= n; i++ {
		if c%i == 0 {
			exp := 0
			for c%i == 0 {
				c /= i
				exp++
			}
			if i%4 == 3 && exp%2 != 0 {
				return false
			}
		}
	}
	return c%4 != 3
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using Two Pointers	Time Complexity: O(sqrt(c)) Space Complexity: O(1)
Mathematical Interpretation and Brute Force	Time Complexity: O(sqrt(c) * log(c)) Space Complexity: O(1)
Mathematics + Two Pointers	–
Mathematics	–

Complexity analysis

Approach	Time	Space	When to Use
Mathematical Brute Force (check perfect square)	O(√c)	O(1)	Good baseline approach. Simple logic when you only need to check one candidate per iteration.
Two Pointers	O(√c)	O(1)	Preferred interview solution. Efficient exploration of pairs without nested loops.
Binary Search for Second Square	O(√c log c)	O(1)	Useful if you want explicit search for the second value instead of pointer movement.

Frequently asked questions

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.

Sum of Square Numbers solution and explanation

The problem

Approach overview

Approach 1: Using Two Pointers

Approach 2: Mathematical Interpretation and Brute Force

Approach 3: Mathematics + Two Pointers

Approach 4: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Sum of Square Numbers solution and explanation

The problem

Approach overview

Approach 1: Using Two Pointers

Approach 2: Mathematical Interpretation and Brute Force

Approach 3: Mathematics + Two Pointers

Approach 4: Mathematics

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems