What is the time complexity of the Brute Force approach?

The Brute Force approach has a time complexity of O(n³) as it iterates through all possible combinations of a, b, and c.

How does the Optimized Brute Force approach improve efficiency?

The Optimized Brute Force approach reduces time complexity to O(n²) by computing c directly from a and b instead of iterating through all c values.

What is the space complexity of the Using Set approach?

The Using Set approach has a space complexity of O(n) to store all squares from 1² to n² in a hash set.

What is the maximum value of n in the constraints?

The maximum value of n is 250, which makes the O(n²) approaches very efficient for this problem.

Count Square Sum Triples

Difficulty: Easy | Acceptance: 77.20% | Paid: No Topics: Math, Enumeration

A square triple (a,b,c) is a triple where a, b, and c are integers and a² + b² = c².

Given an integer n, return the number of square triples (a,b,c) such that 1 <= a, b, c <= n.

Examples
Constraints
Brute Force
Optimized Brute Force
Using Set

Examples

Input: n = 5
Output: 2
Explanation: The square triples are (3,4,5) and (4,3,5).

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

Constraints

1 <= n <= 250

Brute Force

Intuition Check all possible combinations of (a, b, c) from 1 to n and count those satisfying the Pythagorean theorem.

Steps

Iterate through all values of a from 1 to n
Iterate through all values of b from 1 to n
Iterate through all values of c from 1 to n
If a² + b² = c², increment the count

python

class Solution:
    def countTriples(self, n: int) -&gt; int:
        count = 0
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                for c in range(1, n + 1):
                    if a * a + b * b == c * c:
                        count += 1
        return count

Complexity

Time: O(n³)
Space: O(1)
Notes: Simple but inefficient for larger n values

Optimized Brute Force

Intuition Instead of iterating through c, compute c² = a² + b² and check if it’s a perfect square within range.

Steps

Iterate through all values of a from 1 to n
Iterate through all values of b from 1 to n
Calculate c² = a² + b²
Compute c = √(c²) and verify if c² is a perfect square and c ≤ n

python

import math

class Solution:
    def countTriples(self, n: int) -&gt; int:
        count = 0
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                c_squared = a * a + b * b
                c = int(math.isqrt(c_squared))
                if c * c == c_squared and c &lt;= n:
                    count += 1
        return count

Complexity

Time: O(n²)
Space: O(1)
Notes: Eliminates the inner loop for c, significantly improving performance

Using Set

Intuition Precompute all valid squares and use a hash set for O(1) lookup when checking if a² + b² is a valid c².

Steps

Create a set containing all squares from 1² to n²
Iterate through all values of a from 1 to n
Iterate through all values of b from 1 to n
Check if a² + b² exists in the set

python

class Solution:
    def countTriples(self, n: int) -&gt; int:
        squares = {i * i for i in range(1, n + 1)}
        count = 0
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                if a * a + b * b in squares:
                    count += 1
        return count

Complexity

Time: O(n²)
Space: O(n)
Notes: Trades space for cleaner code with O(1) lookup time