# Count Square Sum Triples
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-square-sum-triples)
Canonical: https://scaleengineer.com/dsa/problems/count-square-sum-triples
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Companies:** [Qualtrics](https://scaleengineer.com/companies/qualtrics)
---
## Problem
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`

# Approaches
## Brute-Force with Three Loops
This is the most straightforward but least efficient approach. It involves using three nested loops to iterate through all possible combinations of integers `a`, `b`, and `c` from 1 to `n`. For each combination, it checks if they form a square triple by verifying the equation `a^2 + b^2 = c^2`.
**Time:** O(n^3) - There are three nested loops, and each loop runs up to `n` times, leading to a cubic time complexity. · **Space:** O(1) - We only use a constant amount of extra space for the counter and loop variables.
**Pros:** Very simple to understand and implement.; Requires no extra space besides a few variables.
**Cons:** Highly inefficient due to its cubic time complexity.; Will be very slow or time out for larger values of `n`.
### Explanation
The algorithm systematically checks every single possible triple `(a, b, c)` where each element is between 1 and `n`.

- We initialize a counter variable, `count`, to zero.
- We set up three nested `for` loops. The outer loop iterates `a` from 1 to `n`, the middle loop iterates `b` from 1 to `n`, and the inner loop iterates `c` from 1 to `n`.
- Inside the innermost loop, we compute `a*a + b*b` and compare it with `c*c`.
- If `a*a + b*b == c*c`, we have found a valid square triple, and we increment our `count`.
- After all possible combinations have been checked, the final value of `count` is the answer.

```java
class Solution {
    public int countTriples(int n) {
        int count = 0;
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                for (int c = 1; c <= n; c++) {
                    if (a * a + b * b == c * c) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use three nested loops to iterate `a`, `b`, and `c` from 1 to `n`.
- Inside the innermost loop, check if `a*a + b*b == c*c`.
- If the condition is true, increment `count`.
- After the loops complete, return `count`.

## Optimized Brute-Force with Two Loops
This approach improves upon the brute-force method by eliminating the third loop for `c`. It iterates through all pairs of `a` and `b` and then calculates the required value of `c`. It then checks if this calculated `c` is an integer and falls within the valid range `[1, n]`.
**Time:** O(n^2) - We use two nested loops, each running up to `n` times. The operations inside the loops, including `Math.sqrt`, are considered to take constant time. · **Space:** O(1) - No auxiliary data structures are needed; only a few variables are used for storage.
**Pros:** Significantly more efficient than the O(n^3) approach.; Maintains O(1) space complexity.; Still relatively easy to understand and implement.
**Cons:** Involves floating-point arithmetic (`Math.sqrt`), which can be slightly slower than pure integer operations.
### Explanation
Instead of iterating through `c`, we can derive it from `a` and `b`. This reduces the complexity from cubic to quadratic.

- We iterate through all possible values for `a` and `b` from 1 to `n` using two nested loops.
- For each pair `(a, b)`, we calculate the sum of their squares: `sumSq = a*a + b*b`.
- We then find the potential value of `c` by taking the square root of `sumSq`.
- To ensure `c` is a valid integer, we can cast the result of the square root to an integer and then check if its square equals `sumSq`. For example, `int c = (int) Math.sqrt(sumSq);` and then check `c*c == sumSq`.
- We also must verify that this integer `c` is within the allowed range, i.e., `c <= n`.
- If both conditions are met, we've found a valid triple, and we increment our counter.

```java
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 sumSq = a * a + b * b;
                int c = (int) Math.sqrt(sumSq);
                if (c * c == sumSq && c <= n) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use two nested loops to iterate `a` and `b` from 1 to `n`.
- For each pair `(a, b)`, calculate `sum_sq = a*a + b*b`.
- Calculate `c = sqrt(sum_sq)`.
- Check if `c` is an integer (by verifying `c*c == sum_sq`) and if `c <= n`.
- If both conditions are met, increment `count`.
- Return `count`.

## Optimized Two Loops with Pre-computation
This approach further optimizes the two-loop method by avoiding repeated square root calculations. It pre-computes all perfect squares up to `n*n` and stores them in a hash set. This allows for a constant-time lookup to check if `a^2 + b^2` is a perfect square within the required range.
**Time:** O(n^2) - The pre-computation step takes `O(n)`. The main part consists of two nested loops running in `O(n^2)`, with each hash set lookup taking `O(1)` on average. The total complexity is dominated by the nested loops. · **Space:** O(n) - We need to store `n` perfect squares in the hash set.
**Pros:** Very efficient for the given constraints, often faster in practice than the `sqrt` method.; Avoids floating-point arithmetic, which can prevent potential precision issues.
**Cons:** Uses extra space to store the set of squares, which is a time-space tradeoff.
### Explanation
This method trades space for time. By pre-calculating values, we can make the check inside the loops faster.

- First, we create a `HashSet` to store the squares of all integers from 1 to `n`. We iterate from `i = 1` to `n` and add `i*i` to the set. This gives us a collection of all possible `c*c` values where `c <= n`.
- Next, we use two nested loops to iterate through `a` from 1 to `n` and `b` from 1 to `n`.
- Inside the inner loop, we calculate `sumSq = a*a + b*b`.
- Instead of using `Math.sqrt`, we simply check if `sumSq` is present in our `HashSet`. A successful lookup means there exists an integer `c` such that `c*c = sumSq` and `c <= n`.
- If `sumSq` is found in the set, we increment our counter.
- This approach is generally faster in practice as hash set lookups are very efficient and it avoids floating-point arithmetic.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countTriples(int n) {
        Set<Integer> squares = new HashSet<>();
        for (int i = 1; i <= n; i++) {
            squares.add(i * i);
        }

        int count = 0;
        for (int a = 1; a <= n; a++) {
            for (int b = 1; b <= n; b++) {
                int sumSq = a * a + b * b;
                if (squares.contains(sumSq)) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Create a `HashSet` named `squares`.
- Loop `i` from 1 to `n` and add `i*i` to the `squares` set.
- Initialize `count = 0`.
- Loop `a` from 1 to `n`.
-   Loop `b` from 1 to `n`.
-     Calculate `sum_sq = a*a + b*b`.
-     Check if `sum_sq` exists in the `squares` set.
-     If it does, increment `count`.
- Return `count`.

# Solutions
### Java

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

```

### Python

```python
class Solution:
    def countTriples(self, n: int) -> int: res = 0 for a in range(1, n + 1): for b in range(1, n + 1): t = a ** 2 + b ** 2 c = int(sqrt(t)) if c <= n and c ** 2 == t: res += 1 return res

```

### CPP

```cpp
class Solution {
public:
  int countTriples(int n) {
    int res = 0;
    for (int a = 1; a <= n; ++a) {
      for (int b = 1; b <= n; ++b) {
        int t = a * a + b * b;
        int c = (int)sqrt(t);
        if (c <= n && c * c == t) {
          ++res;
        }
      }
    }
    return res;
  }
};

```