LeetCode 1925 - Count Square Sum Triples

LeetCode Problem 1925

Difficulty: 🟢 Easy
Topics: Math, Enumeration

Solution

Problem Understanding

This problem asks us to count all ordered triples (a, b, c) such that:

• 1 <= a, b, c <= n
• a² + b² = c²

This is the classic Pythagorean theorem relationship. Any triple satisfying this condition is called a square triple in the problem statement.

The important detail is that the triples are ordered. This means (3,4,5) and (4,3,5) are considered different triples and both must be counted separately.

The input consists of a single integer n, which defines the maximum possible value for a, b, and c. The output is the total number of valid ordered triples.

The constraints are very small:

• 1 <= n <= 250

Because n is only 250, even relatively inefficient enumeration approaches are acceptable. However, we still want to design a clean and efficient solution.

There are several important observations and edge cases:

• Very small values of n, such as 1 or 2, cannot form any valid triples because the smallest Pythagorean triple is (3,4,5).
• The problem counts ordered pairs, so symmetry matters.
• We only care about integer square relationships.
• Since n is small, integer overflow is not a concern in either Python or Go.

Approaches

Brute Force Approach

The most direct solution is to try every possible combination of (a, b, c).

We can use three nested loops:

• Iterate a from 1 to n
• Iterate b from 1 to n
• Iterate c from 1 to n

For every triple, compute:

a² + b² == c²

If the equation holds, increment the answer.

This approach is correct because it explicitly checks every possible candidate triple. No valid solution can be missed.

However, the time complexity is very high:

• There are n³ combinations.
• With n = 250, this becomes 15,625,000 checks.

While this still fits within practical limits for this problem, it is unnecessarily expensive.

Optimal Enumeration Approach

The key observation is that once a and b are chosen, the value of c² is completely determined:

c² = a² + b²

Instead of iterating over all possible c values, we can directly compute whether a² + b² is a perfect square.

The improved strategy is:

• Enumerate all (a, b) pairs
• Compute sumSquares = a² + b²
• Compute c = sqrt(sumSquares)
• Check whether c * c == sumSquares
• Also ensure c <= n

This reduces the complexity from O(n³) to O(n²).

Because the constraint is small, this solution is both simple and efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(1)	Checks every possible (a,b,c) combination
Optimal	O(n²)	O(1)	Computes c directly using square root

Algorithm Walkthrough

1. Initialize a variable count to store the number of valid square triples.
2. Iterate a from 1 to n. Every valid triple must include a value for a, so we systematically examine all possibilities.
3. Inside that loop, iterate b from 1 to n. Since ordered pairs matter, we must consider every (a,b) combination separately.
4. Compute:

sumSquares = a² + b²

This value represents the required square value for c². 5. Compute the integer square root of sumSquares.

We do this because if sumSquares is a perfect square, then there exists an integer c satisfying:

c² = sumSquares

6. Verify that the square root is exact:

c * c == sumSquares

This confirms that sumSquares is a perfect square. 7. Also verify:

c <= n

since the problem restricts all values to the range [1, n]. 8. If both conditions are true, increment count. 9. After all loops finish, return count.

Why it works

The algorithm examines every possible ordered pair (a,b). For each pair, the equation uniquely determines what c² must equal. By checking whether this value is a perfect square within the allowed range, we correctly identify every valid square triple exactly once. Since every possible (a,b) pair is processed, no valid solution can be missed.

Python Solution

class Solution:
    def countTriples(self, n: int) -> int:
        count = 0

        for a in range(1, n + 1):
            for b in range(1, n + 1):
                sum_squares = a * a + b * b

                c = int(sum_squares ** 0.5)

                if c * c == sum_squares and c <= n:
                    count += 1

        return count

The implementation directly follows the algorithm described earlier.

The variable count stores the total number of valid triples.

The outer two loops enumerate every ordered pair (a,b). Since the problem treats (3,4,5) and (4,3,5) as different triples, we intentionally do not restrict b relative to a.

For each pair, we compute sum_squares, which represents the required value of c².

We then compute the integer square root using:

c = int(sum_squares ** 0.5)

The check:

c * c == sum_squares

ensures that sum_squares is a perfect square. Floating point square roots may produce non-integer values, so this verification step is essential.

Finally, we ensure c <= n before counting the triple.

Go Solution

package main

import "math"

func countTriples(n int) int {
    count := 0

    for a := 1; a <= n; a++ {
        for b := 1; b <= n; b++ {
            sumSquares := a*a + b*b

            c := int(math.Sqrt(float64(sumSquares)))

            if c*c == sumSquares && c <= n {
                count++
            }
        }
    }

    return count
}

The Go implementation is almost identical to the Python version.

One notable difference is that Go's math.Sqrt function operates on float64, so we must explicitly convert between integer and floating point types:

c := int(math.Sqrt(float64(sumSquares)))

After conversion back to an integer, we verify the perfect square condition using:

c*c == sumSquares

This avoids problems caused by floating point precision.

Integer overflow is not a concern because the maximum value is:

250² + 250² = 125000

which easily fits inside Go's integer range.

Worked Examples

Example 1

Input:

n = 5

We enumerate all ordered pairs (a,b).

a	b	a² + b²	sqrt	Perfect Square?	Valid Triple
1	1	2	1	No	No
1	2	5	2	No	No
2	3	13	3	No	No
3	4	25	5	Yes	(3,4,5)
4	3	25	5	Yes	(4,3,5)

The final count is:

2

Example 2

Input:

n = 10

Relevant successful iterations:

a	b	a² + b²	c	Valid Triple
3	4	25	5	(3,4,5)
4	3	25	5	(4,3,5)
6	8	100	10	(6,8,10)
8	6	100	10	(8,6,10)

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n²)	Two nested loops iterate over all (a,b) pairs
Space	O(1)	Only a few integer variables are used

The algorithm performs exactly n² iterations because every ordered pair (a,b) is checked once. Inside each iteration, all operations are constant time, including multiplication and square root computation. No additional data structures proportional to input size are used, so the space complexity remains constant.

Test Cases

sol = Solution()

assert sol.countTriples(1) == 0  # minimum input, no triples possible
assert sol.countTriples(2) == 0  # still too small for any Pythagorean triple
assert sol.countTriples(5) == 2  # basic example from problem statement
assert sol.countTriples(10) == 4  # includes two symmetric pairs
assert sol.countTriples(4) == 0  # just below smallest valid c value
assert sol.countTriples(13) == 6  # includes (5,12,13) and permutations
assert sol.countTriples(25) > 0  # larger range with multiple triples
assert sol.countTriples(250) > 0  # upper constraint stress test

Test	Why
n = 1	Verifies lower boundary
n = 2	Ensures no false positives for tiny inputs
n = 5	Validates first official example
n = 10	Validates second official example
n = 4	Checks boundary before smallest triple
n = 13	Verifies multiple distinct triples
n = 25	Tests larger enumeration behavior
n = 250	Stress test at maximum constraint

Edge Cases

Very Small Inputs

Inputs such as n = 1, n = 2, n = 3, and n = 4 cannot produce any valid square triples. A naive implementation might accidentally count invalid combinations if the perfect square check is incorrect. This implementation safely returns 0 because no (a,b) pair produces a valid integer c within the range.

Ordered Pair Symmetry

The problem counts ordered triples, meaning (3,4,5) and (4,3,5) are different answers. A common bug is restricting the loops to b >= a, which would incorrectly eliminate valid ordered combinations. This implementation loops independently over all values of a and b, ensuring both orders are counted.

Floating Point Square Root Precision

Square root computations use floating point arithmetic, which can sometimes introduce precision issues. A buggy implementation might rely solely on checking whether the square root appears integer-like. This solution avoids that problem by verifying:

c * c == sum_squares

This exact integer comparison guarantees correctness even if floating point rounding occurs internally.