Problem Description

The Count Square Sum Triples problem asks you to count the number of square sum triples that can be formed using integers from 1 to n (inclusive), where n is a positive integer input.

A square sum triple is a set of three integers (a, b, c) such that:

• Each of a, b, and c is between 1 and n (inclusive).
• a^2 + b^2 = c^2.
• a and b can be in any order (i.e., both (a, b, c) and (b, a, c) are counted as separate triples if a ≠ b).

The goal is to return the total number of such triples for a given n.

Thought Process

To approach this problem, let's first think about what it means for a^2 + b^2 = c^2. This is the classic Pythagorean triple relationship. For all numbers from 1 to n, we want to find all ordered pairs (a, b) such that their squares sum up to a perfect square c^2, with c also between 1 and n.

A straightforward way is to check every possible combination of a, b, and c. However, this is inefficient. Instead, we can optimize by:

• Fixing c from 1 to n, then finding all pairs (a, b) such that a^2 + b^2 = c^2 and a, b ≤ n.
• For each c, iterate a from 1 to n, compute b^2 = c^2 - a^2, and check if b is an integer between 1 and n.
• Count both (a, b, c) and (b, a, c) if a ≠ b.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Iterate over possible values of c:
   • For each c from 1 to n, compute c^2.
2. For each c, iterate over possible values of a:
   • For each a from 1 to n, compute a^2.
   • Calculate b^2 = c^2 - a^2.
3. Check if b^2 is a perfect square:
   • If b^2 > 0, compute b = sqrt(b^2).
   • If b is an integer and 1 ≤ b ≤ n, then (a, b, c) is a valid triple.
   • We count each triple, including when a = b.
4. Count all valid triples:
   • Since both (a, b, c) and (b, a, c) are counted, we do not filter out duplicates.
5. Return the total count.

This approach ensures we only check valid possibilities and avoids unnecessary iterations.

Example Walkthrough

Let's consider n = 5. We want to find all triples (a, b, c) where 1 ≤ a, b, c ≤ 5 and a^2 + b^2 = c^2.

• For c = 5, c^2 = 25:
  • Try a = 3: a^2 = 9, so b^2 = 25 - 9 = 16, b = 4 (valid, since 1 ≤ 4 ≤ 5).
  • So, (3, 4, 5) and (4, 3, 5) are both valid triples.
• Other combinations for c = 5 do not yield integer b between 1 and 5.
• For other values of c (1 to 4), no valid triples exist.

So, the answer for n = 5 is 2 (the triples (3, 4, 5) and (4, 3, 5)).

Time and Space Complexity

Brute-force Approach:

• Check all possible (a, b, c) with 1 ≤ a, b, c ≤ n.
• This is O(n^3) time, since there are n^3 combinations.
• Space is O(1), as we only count valid triples.

• Iterate c from 1 to n (n iterations).
• For each c, iterate a from 1 to n (n iterations).
• For each pair, compute b^2 = c^2 - a^2, check if b is integer and in range.
• Total time: O(n^2). This is much faster for larger n.
• Space is still O(1).

Summary

The Count Square Sum Triples problem is a variation of finding Pythagorean triples within a limited range. The key insight is to fix c and search for pairs (a, b) such that a^2 + b^2 = c^2, optimizing the search to O(n^2) time. This makes it efficient even for larger values of n. The approach is systematic, avoids unnecessary computation, and leverages the properties of perfect squares and integer arithmetic to find all valid triples.

Code Implementation

class Solution:
    def countTriples(self, n: int) -> int:
        count = 0
        for c in range(1, n + 1):
            c2 = c * c
            for a in range(1, n + 1):
                b2 = c2 - a * a
                b = int(b2 ** 0.5)
                if b > 0 and b <= n and b * b == b2:
                    count += 1
        return count
      

class Solution {
public:
    int countTriples(int n) {
        int count = 0;
        for (int c = 1; c <= n; ++c) {
            int c2 = c * c;
            for (int a = 1; a <= n; ++a) {
                int b2 = c2 - a * a;
                int b = (int)sqrt(b2);
                if (b > 0 && b <= n && b * b == b2) {
                    count++;
                }
            }
        }
        return count;
    }
};
      

class Solution {
    public int countTriples(int n) {
        int count = 0;
        for (int c = 1; c <= n; ++c) {
            int c2 = c * c;
            for (int a = 1; a <= n; ++a) {
                int b2 = c2 - a * a;
                int b = (int)Math.sqrt(b2);
                if (b > 0 && b <= n && b * b == b2) {
                    count++;
                }
            }
        }
        return count;
    }
}
      

var countTriples = function(n) {
    let count = 0;
    for (let c = 1; c <= n; ++c) {
        let c2 = c * c;
        for (let a = 1; a <= n; ++a) {
            let b2 = c2 - a * a;
            let b = Math.sqrt(b2);
            if (b > 0 && b <= n && Number.isInteger(b)) {
                count++;
            }
        }
    }
    return count;
};