Sum of Square Numbers · Interview Problem

Back to problems

Leetcode

Medium

Math

Number Theory

Two Pointers

Sum of Square Numbers

Determine whether a non-negative integer can be written as the sum of two perfect squares.

Acceptance 75%

Start Practice

Problem Statement

Problem

Given a non-negative integer c, determine whether there exist integers a and b such that:

$a^2 + b^2 = c$

Return true if such a pair exists, otherwise return false.

You may use the same value for a and b. The integers are not required to be distinct.

Input Format

A single integer c.

Output Format

Return true if c can be expressed as the sum of two square numbers.
Otherwise return false.

Constraints

$0 \le c$
The value fits in a standard 32-bit signed integer.

Hints

Try searching for two numbers whose squares add up to c.
If one square is too large, reduce it instead of trying all pairs blindly.

Input Format

A single integer c.

Output Format

Return true if c = a^2 + b^2 for some integers a and b.
Otherwise return false.

Constraints

$0 \le c$
c fits in a 32-bit signed integer.

Examples

Sample cases returned by the problem API.

Example 1

Input

c = 5

Output

true

Explanation

Because $1^2 + 2^2 = 5$ .

Example 2

Input

c = 3

Output

false

Explanation

There are no integers a and b such that $a^2 + b^2 = 3$ .

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress