Count Square Sum Triples

Easy
553.

Count Square Sum Triples

Count Square Sum Triples is an easy coding problem on math and enumeration, asked in Amazon and TCS interviews.

A square triple is an ordered triple (a, b, c) of positive integers with a² + b² = c².

Given an integer n, return the number of square triples with 1 <= a, b, c <= n. Order matters, so (3,4,5) and (4,3,5) count separately.

Example 1

Input
n = 5
Output
2
Explanation
(3,4,5) and (4,3,5).

Example 2

Input
n = 10
Output
4
Explanation
The Pythagorean triples within range are (3,4,5), (4,3,5), (6,8,10) and (8,6,10).

Example 3

Input
n = 2
Output
0

Constraints

  • 1 <= n <= 250
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var countTriples = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Square Sum Triples — Solution in Python, Java & C++

Count Square Sum Triples solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Count Square Sum Triples is an easy coding problem on math and enumeration, asked in Amazon and TCS interviews.

  • Difficulty: Easy
  • Topics: Math, Enumeration
  • Asked at: Amazon, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A square triple is an ordered triple (a, b, c) of positive integers with a² + b² = c².

Given an integer n, return the number of square triples with 1 <= a, b, c <= n. Order matters, so (3,4,5) and (4,3,5) count separately.

Example 1

Input: n = 5
Output: 2
Explanation: (3,4,5) and (4,3,5).

Example 2

Input: n = 10
Output: 4
Explanation: The Pythagorean triples within range are (3,4,5), (4,3,5), (6,8,10) and (8,6,10).

Example 3

Input: n = 2
Output: 0

Constraints

  • 1 <= n <= 250

Hints for Count Square Sum Triples

  1. Hint 1

    n is at most 250, so a double loop over a and b is only 62,500 iterations.

  2. Hint 2

    For each pair, c is determined: it is sqrt(a² + b²).

  3. Hint 3

    Check that the square root is an exact integer and does not exceed n.

How to solve Count Square Sum Triples

Enumerating a and b fixes c, so the third value never needs its own loop — only an exact-square test.

Approach

  1. Loop a and b each from 1 to n.
  2. Compute s = a² + b² and c = round(sqrt(s)).
  3. Count the triple when c <= n and c * c == s.

Why it works

c is uniquely determined by a and b, so each ordered pair contributes at most one triple. Rounding before the squaring check makes the integer test exact despite floating-point square roots.

Complexity

  • Time — O(n²)
  • Space — O(1)

Pitfalls

  • Truncating the square root instead of rounding can miss exact squares by one because of floating-point error — always verify with c * c == s.
  • A triple loop over a, b and c is O(n³) — 15 million iterations here, still passable but wasteful.
  • Counting only a < b halves the answer; the problem counts ordered pairs.

Reference solution

Python

def countTriples(n: int) -> int:
    count = 0
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            s = a * a + b * b
            c = int(s ** 0.5 + 0.5)
            if c <= n and c * c == s:
                count += 1
    return count

Java

public static int countTriples(int n) {
    int count = 0;
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            int s = a * a + b * b;
            int c = (int) Math.round(Math.sqrt(s));
            if (c <= n && c * c == s) count++;
        }
    }
    return count;
}

C++

int countTriples(int n) {
    int count = 0;
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            int s = a * a + b * b;
            int c = (int) (sqrt((double) s) + 0.5);
            if (c <= n && c * c == s) count++;
        }
    }
    return count;
}

JavaScript

var countTriples = function(n) {
    let count = 0;
    for (let a = 1; a <= n; a++) {
        for (let b = 1; b <= n; b++) {
            const s = a * a + b * b;
            const c = Math.round(Math.sqrt(s));
            if (c <= n && c * c === s) count++;
        }
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 337 math problems · the whole catalogue