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
Hint 1
nis at most 250, so a double loop overaandbis only 62,500 iterations.Hint 2
For each pair,
cis determined: it issqrt(a² + b²).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
- Loop
aandbeach from 1 ton. - Compute
s = a² + b²andc = round(sqrt(s)). - Count the triple when
c <= nandc * 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,bandcis O(n³) — 15 million iterations here, still passable but wasteful. - Counting only
a < bhalves 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 countJava
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.