Count Square Sum Triples

easy math enumeration

Problem

A square triple is a group of three positive integers (a, b, c) such that a² + b² = c². Given an integer n, return the number of square triples whose three values are each at least 1 and at most n. The triples are ordered, so (a, b, c) and (b, a, c) count separately.

Inputn = 5

Output2

The square triples are (3, 4, 5) and (4, 3, 5): both give 9 + 16 = 25 = 5², and every value is between 1 and 5.

def count_triples(n):
    count = 0
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            s = a * a + b * b
            c = int(s ** 0.5)
            if c <= n and c * c == s:
                count += 1
    return count

function countTriples(n) {
  let count = 0;
  for (let a = 1; a <= n; a++) {
    for (let b = 1; b <= n; b++) {
      const s = a * a + b * b;
      const c = Math.floor(Math.sqrt(s));
      if (c <= n && c * c === s) count++;
    }
  }
  return count;
}

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

int countTriples(int n) {
    int count = 0;
    for (int a = 1; a <= n; a++) {
        for (int b = 1; b <= n; b++) {
            int s = a * a + b * b;
            int c = (int) sqrt((double) s);
            if (c <= n && c * c == s) count++;
        }
    }
    return count;
}

Explanation

We need to count ordered triples (a, b, c) with every value in the range [1, n] that satisfy the Pythagorean equation a² + b² = c².

The clean idea is to pick the two legs a and b ourselves and let c be determined. If a valid c exists, it must equal √(a² + b²). So for every pair we compute the sum of squares s = a² + b² and check whether s is a perfect square.

To test that, we take c = floor(√s) and verify two things: c * c == s (so s really is a perfect square) and c ≤ n (so the hypotenuse also fits in range). When both hold, we have found one valid triple and increase the counter.

Example: n = 5. Almost every pair fails the perfect-square test. But at a = 3, b = 4 we get s = 9 + 16 = 25, and √25 = 5 ≤ 5, so that is a hit. At a = 4, b = 3 we get the same 25 and another hit. No other pair works, so the answer is 2.

Because we never have to guess c separately, two nested loops over a and b are enough, which keeps the work down to a square in n.

Time: O(n²) Space: O(1)