Sum of Square Numbers - Practice Coding Problems

Sum of Square Numbers - Problem

Given a non-negative integer c, determine whether there exist two integers a and b such that a² + b² = c.

Return true if such integers exist, otherwise return false.

Note: Both a and b can be zero or negative, but for this problem we only consider non-negative values where a ≥ 0 and b ≥ 0.

Input & Output

Example 1 — Basic True Case

$ Input: c = 5

› Output: true

💡 Note: 1² + 2² = 1 + 4 = 5, so there exist integers a=1 and b=2 such that a² + b² = c

Example 2 — Perfect Square

$ Input: c = 4

› Output: true

💡 Note: 0² + 2² = 0 + 4 = 4 (or 2² + 0² = 4), so it can be expressed as sum of two squares

Example 3 — Impossible Case

$ Input: c = 3

› Output: false

💡 Note: No combination of two squares equals 3: 0²+0²=0, 0²+1²=1, 1²+1²=2, 0²+2²=4. None equal 3.

Constraints

0 ≤ c ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

Given integer c = 5

Process

Find if c can be written as a² + b²

Output

Return true if possible, false otherwise

Key Takeaway

🎯 Key Insight: Only check values up to √c since larger values would make the sum exceed c

Asked in

F Facebook 25 G Google 20 M Microsoft 15

The key insight is that we only need to check values up to √c since both squares can't exceed that. Best approach is two pointers starting from 0 and √c, adjusting based on sum comparison. Time: O(√c), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search Optimization	O(√c log √c)	O(1)	For each a, use binary search to find if √(c - a²) exists
Two Pointers	O(√c)	O(1)	Use two pointers from 0 and √c, adjust based on sum comparison
Brute Force	O(√c)	O(1)	Check all possible pairs (a,b) where a² + b² = c

Binary Search Optimization — Algorithm Steps

Iterate a from 0 to √c
Calculate target = c - a²
Binary search for b where b² = target
Return true if exact match found

Visualization

Tap to expand

Step-by-Step Walkthrough

For a=1

Need to check if c-1²=4 is perfect square

Binary Search

Search for b where b²=4 in range [0,2]

Found b=2

2²=4, so we found valid pair (1,2)

Code -

solution.c — C

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

bool binarySearchSqrt(int target) {
    if (target < 0) return false;
    int left = 0, right = (int) sqrt(target) + 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        long long square = (long long) mid * mid;
        if (square == target) {
            return true;
        } else if (square < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return false;
}

bool solution(int c) {
    for (int a = 0; a <= (int) sqrt(c); a++) {
        int bSquared = c - a * a;
        if (binarySearchSqrt(bSquared)) {
            return true;
        }
    }
    return false;
}

int main() {
    int c;
    scanf("%d", &c);
    bool result = solution(c);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(√c log √c)

√c iterations, each with binary search taking log √c time

⚡ Linearithmic

Space Complexity

O(1)

Only using variables for binary search bounds and calculations

✓ Linear Space

42.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler