Count Square Sum Triples - Practice Coding Problems

Count Square Sum Triples - Problem

Math Enumeration Easy

A square triple (a,b,c) is a triple where a, b, and c are integers and a² + b² = c².

Given an integer n, return the number of square triples such that 1 ≤ a, b, c ≤ n.

For example, if n = 5, the square triples are (3,4,5) and (4,3,5), so the answer is 2.

Input & Output

Example 1 — Basic Case

$ Input: n = 5

› Output: 2

💡 Note: The square triples are (3,4,5) and (4,3,5). Both satisfy 3² + 4² = 9 + 16 = 25 = 5² and all values are ≤ 5.

Example 2 — Small Range

$ Input: n = 3

› Output: 0

💡 Note: No valid square triples exist with all values ≤ 3. The smallest Pythagorean triple is (3,4,5) but 4 and 5 exceed the limit.

Example 3 — Larger Range

$ Input: n = 10

› Output: 4

💡 Note: Valid triples: (3,4,5), (4,3,5), (6,8,10), (8,6,10). Each satisfies the Pythagorean theorem with all values ≤ 10.

Constraints

1 ≤ n ≤ 250

Visualization

Tap to expand

Understanding the Visualization

Input

Given n=5, find all (a,b,c) where a²+b²=c² and 1≤a,b,c≤5

Process

Check all combinations for Pythagorean relationship

Output

Count of valid triples: 2

Key Takeaway

🎯 Key Insight: Use the Pythagorean theorem to identify valid right triangle integer sides

Asked in

G Google 25 M Microsoft 20 A Apple 15

The key insight is using the Pythagorean theorem a² + b² = c² to identify valid square triples. Best approach is the two-loop optimization that calculates c from each (a,b) pair and validates it. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Loop with Square Root	O(n²)	O(1)	Calculate c from a and b, then check if c is valid
Triple Loop Brute Force	O(n³)	O(1)	Check all possible combinations of three numbers

Two Loop with Square Root — Algorithm Steps

Step 1: Loop through all values of a from 1 to n
Step 2: Loop through all values of b from 1 to n
Step 3: Calculate c² = a² + b²
Step 4: Check if c is an integer and c ≤ n

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate (a,b) pairs

Try all combinations of a and b

Calculate c

c = √(a² + b²)

Validate

Check if c is integer and c ≤ n

Code -

solution.c — C

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

int solution(int n) {
    int count = 0;
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            int cSquared = a * a + b * b;
            int c = (int)sqrt(cSquared);
            if (c * c == cSquared && c <= n) {
                count++;
            }
        }
    }
    return count;
}

int main() {
    int n;
    scanf("%d", &n);
    int result = solution(n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two nested loops each running n times

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a few variables for calculations

✓ Linear Space

32.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

Two Loop with Square Root — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler