{x}
blog image

Count Square Sum Triples

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

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

 

Example 1:

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

Example 2:

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

Solution Explanation: Count Square Sum Triples

This problem asks us to find the number of Pythagorean triples (a, b, c) where 1 ≤ a, b, c ≤ n and a² + b² = c². The most straightforward approach is brute force enumeration.

Approach: Brute Force Enumeration

We iterate through all possible integer pairs (a, b) within the range [1, n). For each pair, we calculate c² = a² + b². If c² is a perfect square and c is within the range [1, n], then (a, b, c) is a valid square triple, and we increment our count.

Time Complexity Analysis

The nested loops iterate through approximately n² pairs (a, b). The calculation of c² and the square root check are constant time operations. Therefore, the overall time complexity is O(n²).

Space Complexity Analysis

The algorithm uses only a few variables to store the current values of a, b, c, and the count. The space used does not depend on the input size n, so the space complexity is O(1), constant space.

Code Implementation in Various Languages

Python3

import math
 
class Solution:
    def countTriples(self, n: int) -> int:
        ans = 0
        for a in range(1, n):
            for b in range(1, n):
                c_squared = a*a + b*b
                c = int(math.sqrt(c_squared))
                if c * c == c_squared and c <= n:
                    ans += 1
        return ans

Java

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

C++

#include <cmath>
 
class Solution {
public:
    int countTriples(int n) {
        int ans = 0;
        for (int a = 1; a < n; ++a) {
            for (int b = 1; b < n; ++b) {
                long long cSquared = (long long)a * a + (long long)b * b;
                int c = sqrt(cSquared);
                if ((long long)c * c == cSquared && c <= n) {
                    ++ans;
                }
            }
        }
        return ans;
    }
};

Go

import "math"
 
func countTriples(n int) int {
	ans := 0
	for a := 1; a < n; a++ {
		for b := 1; b < n; b++ {
			cSquared := float64(a*a + b*b)
			c := int(math.Sqrt(cSquared))
			if float64(c*c) == cSquared && c <= n {
				ans++
			}
		}
	}
	return ans
}

TypeScript

function countTriples(n: number): number {
    let ans = 0;
    for (let a = 1; a < n; a++) {
        for (let b = 1; b < n; b++) {
            let cSquared = a * a + b * b;
            let c = Math.floor(Math.sqrt(cSquared));
            if (c * c === cSquared && c <= n) {
                ans++;
            }
        }
    }
    return ans;
}

All these implementations follow the same basic logic, differing only in syntax and specific library functions used for square root calculation. The core algorithm remains the brute-force enumeration with O(n²) time complexity and O(1) space complexity. Note that in C++, we use long long to avoid potential integer overflow when calculating cSquared. Similar care should be taken in other languages if n is large.