1925. Count Square Sum Triples

1925. Count Square Sum Triples

Difficulty: Easy

Topics: Math, Enumeration, Biweekly Contest 56

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 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: 2
• Explanation: The square triples are (3,4,5) and (4,3,5).

Constraints:

• 1 <= n <= 250

Hint:

1. Iterate over all possible pairs (a,b) and check that the square root of a * a + b * b is an integers less than or equal n
2. You can check that the square root of an integer is an integer using binary seach or a builtin function like sqrt

Solution:

We are given n and need to count triples (a, b, c) such that a² + b² = c², with 1 <= a, b, c <= n.
The problem is to count all such triples.

We can solve by iterating over a and b, then checking if a² + b² is a perfect square and that its square root (c) is <= n.

However, note that the examples show that (3,4,5) and (4,3,5) are counted as two separate triples because the order of a and b matters.

Approach:

• Precompute all perfect squares from 1 to n and store them in a set for O(1) lookup
• Iterate through all possible pairs (a, b) where a ≤ b ≤ n to avoid duplicate counting
• For each pair, check if a² + b² is a perfect square present in our set
• If found, count both permutations (a,b,c) and (b,a,c) when a ≠ b, otherwise count once when a = b
• Return the total count

Let's implement this solution in PHP: 1925. Count Square Sum Triples

<?php
/**
 * @param Integer $n
 * @return Integer
 */
function countTriples($n) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo countTriples(5) . "\n";        // Output: 2
echo countTriples(10) . "\n";       // Output: 4
?>

Explanation:

• Precomputation: Create a lookup set of all c² values where 1 ≤ c ≤ n
• Efficient Checking: Instead of calculating square roots for each pair, use the set to check if a² + b² exists
• Counting Logic:
  • When a = b, only one unique ordering exists: (a, b, c)
  • When a ≠ b, two orderings exist: (a, b, c) and (b, a, c)
• Complexity: O(n²) time and O(n) space, which is efficient for n ≤ 250
• Edge Cases: Handles n = 1 correctly (returns 0 as no valid triples exist)

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub