Problem Description

A square triple (a, b, c) is a triple of integers where a² + b² = c². This is essentially a Pythagorean triple - three numbers that satisfy the Pythagorean theorem.

Given an integer n, you need to find and return the total count of all square triples (a, b, c) where each of a, b, and c are integers between 1 and n inclusive.

For example, if n = 5, the triple (3, 4, 5) would be valid because 3² + 4² = 9 + 16 = 25 = 5², and all three numbers are within the range [1, 5]. Similarly, (4, 3, 5) would also be valid and counted separately.

The solution iterates through all possible values of a and b from 1 to n-1, calculates c as the square root of a² + b², and checks if c is a perfect square (integer) and within the allowed range. Each valid triple found increments the counter.

Intuition

The key insight is recognizing that we need to find all Pythagorean triples within a bounded range. Since we're looking for triples (a, b, c) where a² + b² = c², we can use a brute force approach given the constraint that all values must be at most n.

The natural approach is to try all possible combinations of a and b, then check if they form a valid triple. For each pair (a, b), we can directly calculate what c should be using the formula c = √(a² + b²).

Why does this work? Because if a valid triple exists, c is uniquely determined by a and b. We don't need to try all possible values of c separately - we can compute it directly and then verify two conditions:

1. Is c an integer? (meaning √(a² + b²) is a perfect square)
2. Is c ≤ n? (meaning it's within our allowed range)

The check for whether c is an integer is done by computing c = int(sqrt(x)) where x = a² + b², then verifying that c² == x. If c were not an integer, then int(sqrt(x)) would truncate the decimal part, and squaring it back wouldn't give us the original x.

Note that we enumerate a and b from 1 to n-1 (not including n) because even if a = n or b = n, the resulting c would be strictly greater than n (since c² = a² + b² > a² when b > 0), violating our constraint.

Learn more about Math patterns.

Solution Approach

The implementation uses a nested loop enumeration approach to find all valid square triples:

1. Outer loop: Iterate a from 1 to n-1
2. Inner loop: For each a, iterate b from 1 to n-1
3. Calculate potential c: For each pair (a, b), compute x = a * a + b * b which represents a² + b²
4. Extract integer square root: Calculate c = int(sqrt(x)) to get the integer part of the square root
5. Validate the triple: Check two conditions:
   • c <= n: Ensures c is within the allowed range
   • c * c == x: Verifies that c is indeed the exact square root of x (not truncated)
6. Count valid triples: If both conditions are met, increment the answer counter by 1

The algorithm systematically checks all possible combinations of a and b values. For each combination, it determines if a valid c exists that satisfies the Pythagorean theorem within the given constraints.

Time Complexity: O(n²) as we have two nested loops each running approximately n times.

Space Complexity: O(1) as we only use a constant amount of extra space for variables.

The key insight in the implementation is that we don't need to enumerate c separately. By calculating c directly from a and b, we reduce what would be an O(n³) brute force approach to an O(n²) solution.

Example Walkthrough

Let's walk through the algorithm with n = 5 to find all square triples.

Step 1: Initialize

• Set answer = 0
• We'll check all pairs (a, b) where a and b range from 1 to 4

Step 2: Iterate through all combinations

When a = 1:

• b = 1: x = 1² + 1² = 2, c = int(√2) = 1, check: 1² = 1 ≠ 2 ❌
• b = 2: x = 1² + 2² = 5, c = int(√5) = 2, check: 2² = 4 ≠ 5 ❌
• b = 3: x = 1² + 3² = 10, c = int(√10) = 3, check: 3² = 9 ≠ 10 ❌
• b = 4: x = 1² + 4² = 17, c = int(√17) = 4, check: 4² = 16 ≠ 17 ❌

When a = 2:

• b = 1: x = 2² + 1² = 5, c = int(√5) = 2, check: 2² = 4 ≠ 5 ❌
• b = 2: x = 2² + 2² = 8, c = int(√8) = 2, check: 2² = 4 ≠ 8 ❌
• b = 3: x = 2² + 3² = 13, c = int(√13) = 3, check: 3² = 9 ≠ 13 ❌
• b = 4: x = 2² + 4² = 20, c = int(√20) = 4, check: 4² = 16 ≠ 20 ❌

When a = 3:

• b = 1: x = 3² + 1² = 10, c = int(√10) = 3, check: 3² = 9 ≠ 10 ❌
• b = 2: x = 3² + 2² = 13, c = int(√13) = 3, check: 3² = 9 ≠ 13 ❌
• b = 3: x = 3² + 3² = 18, c = int(√18) = 4, check: 4² = 16 ≠ 18 ❌
• b = 4: x = 3² + 4² = 25, c = int(√25) = 5
  • Check 1: c = 5 ≤ n = 5 ✓
  • Check 2: 5² = 25 = x ✓
  • Valid triple found! (3, 4, 5), answer = 1

When a = 4:

• b = 1: x = 4² + 1² = 17, c = int(√17) = 4, check: 4² = 16 ≠ 17 ❌
• b = 2: x = 4² + 2² = 20, c = int(√20) = 4, check: 4² = 16 ≠ 20 ❌
• b = 3: x = 4² + 3² = 25, c = int(√25) = 5
  • Check 1: c = 5 ≤ n = 5 ✓
  • Check 2: 5² = 25 = x ✓
  • Valid triple found! (4, 3, 5), answer = 2
• b = 4: x = 4² + 4² = 32, c = int(√32) = 5, check: 5² = 25 ≠ 32 ❌

Step 3: Return result

• Total valid square triples found: 2
• The triples are (3, 4, 5) and (4, 3, 5)

This example demonstrates how the algorithm efficiently finds Pythagorean triples by:

1. Systematically checking all (a, b) pairs
2. Computing the required c value directly
3. Validating that c is both an integer and within bounds
4. Counting each valid triple separately (even if they're permutations like (3,4,5) and (4,3,5))

Solution Implementation

Time and Space Complexity

The time complexity is O(n^2), where n is the given integer. This is because we have two nested loops, each iterating from 1 to n-1, resulting in approximately n * n iterations. Within each iteration, we perform constant time operations: calculating a * a + b * b, computing the square root, and checking if c * c == x, all of which are O(1) operations.

The space complexity is O(1). The algorithm only uses a fixed amount of extra space for variables ans, a, b, x, and c, regardless of the input size n. No additional data structures that grow with the input size are created.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Floating-Point Precision Issues

The most critical pitfall in this solution is relying on floating-point arithmetic for checking perfect squares. Using int(math.sqrt(sum_of_squares)) can lead to incorrect results due to floating-point precision errors.

Problem Example:

# For large values, sqrt might return something like 4.999999999999
# which truncates to 4 instead of 5
sum_of_squares = 25
c = int(math.sqrt(sum_of_squares))  # Might get 4 instead of 5 due to precision

Solution: Avoid floating-point operations entirely by using integer arithmetic:

def countTriples(self, n: int) -> int:
    count = 0
    # Pre-compute squares for O(1) lookup
    squares = {i * i for i in range(1, n + 1)}
  
    for a in range(1, n):
        for b in range(1, n):
            sum_of_squares = a * a + b * b
            # Check if sum_of_squares is a perfect square and within range
            if sum_of_squares in squares:
                count += 1
  
    return count

2. Inefficient Range Boundaries

The current solution iterates a and b from 1 to n-1, but this misses valid triples where a or b equals n.

Problem:

# If n = 5, the loop misses checking (5, 0, 5) type cases
# Though (5, 0, 5) isn't valid since b must be >= 1
# But it does miss cases like when a or b could be n
for a in range(1, n):  # Goes up to n-1, not n

Solution:

for a in range(1, n + 1):  # Include n in the range
    for b in range(1, n + 1):

3. Redundant Computation

Computing a * a repeatedly in the inner loop is inefficient.

Problem:

for a in range(1, n):
    for b in range(1, n):
        sum_of_squares = a * a + b * b  # a*a computed n times unnecessarily

Solution:

for a in range(1, n + 1):
    a_squared = a * a  # Compute once per outer loop
    for b in range(1, n + 1):
        sum_of_squares = a_squared + b * b

4. Missing Early Termination Optimization

The solution continues checking even when it's impossible to find valid triples.

Problem: When a * a + b * b > n * n, no valid c can exist, but the loop continues.

Solution:

for a in range(1, n + 1):
    a_squared = a * a
    if a_squared + 1 > n * n:  # Minimum b is 1
        break
    for b in range(1, n + 1):
        sum_of_squares = a_squared + b * b
        if sum_of_squares > n * n:  # c would exceed n
            break
        # Check for valid triple