Count Square Sum Triples: Enumerating Pythagorean Triples

LeetCode 1925: Count Square Sum Triples gives you a positive integer n and asks you to count the number of square triples (a, b, c) where a * a + b * b == c * c and 1 <= a, b, c <= n. If you have seen Pythagorean triples before, this is exactly that, but you need to count every ordered pair, not just the unique triangles. That means (3, 4, 5) and (4, 3, 5) are two separate triples.

The constraint is small (n <= 250), so a brute-force enumeration of all pairs (a, b) works perfectly. For each pair, you compute a*a + b*b, check whether the result is a perfect square, and verify the root is at most n. That is the entire algorithm.

The approach

The plan is to iterate over every pair (a, b) where 1 <= a <= n and 1 <= b <= n. For each pair:

1. Compute c_sq = a * a + b * b.
2. Compute c = isqrt(c_sq) (the integer square root).
3. If c * c == c_sq (meaning c_sq is a perfect square) and c <= n, you have a valid triple. Increment your counter.

Why does step 3 work? The integer square root isqrt(c_sq) gives you the largest integer whose square is at most c_sq. If that integer, when squared, gives you exactly c_sq back, then c_sq is a perfect square. Otherwise it is not.

You do not need to enumerate c as a third loop variable. Computing it directly from a and b keeps the solution at O(n^2) instead of O(n^3).

The code

import math

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

The two nested loops cover all ordered pairs. Inside, math.isqrt gives the integer square root in O(1) time, and the perfect-square check is a single comparison. No floating-point rounding issues, no epsilon comparisons. The isqrt function is exact.

One thing to note: you could also use int(math.sqrt(c_sq)) instead of math.isqrt, but math.isqrt is preferred because it avoids floating-point precision problems. For large values of c_sq, math.sqrt can return a float that rounds incorrectly, while math.isqrt always returns the exact integer floor.

Step-by-step walkthrough

Let's trace through n = 10. Most pairs will not produce a perfect square, so we will focus on the interesting iterations.

Complexity

Time: O(n^2). Two nested loops from 1 to n. Inside each iteration, the work is O(1): one multiplication, one isqrt call, one comparison.

Space: O(1). Only a handful of integer variables. No auxiliary arrays or data structures.

With n <= 250, the inner loop runs at most 62,500 times. That finishes in under a millisecond on any modern machine.

Building blocks

This problem decomposes into two reusable pieces.

1. Exhaustive pair enumeration

When the search space is small enough, iterating over all pairs is a valid and often the simplest approach. Two nested loops over the range [1, n] give you every ordered pair (a, b). You will see this same enumeration pattern in problems like counting pairs with a given sum, finding matching elements, or brute-force search on small inputs.

for a in range(1, n + 1):
    for b in range(1, n + 1):
        # check some condition on (a, b)

2. Perfect square check with integer square root

To test whether a number x is a perfect square without floating-point rounding errors, compute c = isqrt(x) and verify c * c == x. This micro-pattern shows up in problems like Valid Perfect Square and Sum of Square Numbers. It is a reliable building block whenever you need exact square-root testing.

c = math.isqrt(x)
if c * c == x:
    # x is a perfect square

Edge cases

• n = 1: No triple exists because the smallest Pythagorean triple is (3, 4, 5). Both loops run once with a = 1, b = 1, giving c_sq = 2, which is not a perfect square. Returns 0.
• n = 4: Still no valid triples. The smallest c value is 5, which exceeds n = 4. Returns 0.
• n = 5: The first triples appear: (3, 4, 5) and (4, 3, 5). Returns 2.
• n = 10: Four triples total. In addition to the two from n = 5, you also get (6, 8, 10) and (8, 6, 10) since c = 10 is now within range.

From understanding to recall

The algorithm is short: two loops, one square root, one comparison. But when you sit down to code it from scratch, the small decisions matter. Do you use math.isqrt or math.sqrt? Is the check c * c == c_sq or c_sq == c * c? Do you need c <= n or c < n?

These details are easy to second-guess under pressure. Spaced repetition removes the doubt. After writing the solution a few times at increasing intervals, the pattern of "enumerate pairs, compute sum of squares, check perfect square, verify range" becomes automatic. You stop thinking about whether isqrt rounds down or up because you have verified it yourself multiple times.

The key insight to lock in is: you do not need a third loop for c. Computing c directly from a and b is the move that keeps the solution efficient and clean.

Related posts

• Valid Perfect Square - binary search for testing whether a number is a perfect square
• Sum of Square Numbers - two-pointer search for a pair of squares summing to a target
• Count Primes - another enumeration-style math problem using the Sieve of Eratosthenes