1925. Count Square Sum Triples #2510
-
|
Topics: A square triple Given an integer Example 1:
Example 2:
Constraints:
Hint:
|
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 2 replies
-
|
We are given n and need to count 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:
Let's implement this solution in PHP: 1925. Count Square Sum Triples <?php
/**
* @param Integer $n
* @return Integer
*/
function countTriples($n) {
$count = 0;
// Create a set of all squares for quick lookup
$squareSet = [];
for ($i = 1; $i <= $n; $i++) {
$squareSet[$i * $i] = true;
}
// Iterate through unique pairs
for ($a = 1; $a <= $n; $a++) {
$aSquare = $a * $a;
for ($b = $a; $b <= $n; $b++) {
$sum = $aSquare + $b * $b;
if (isset($squareSet[$sum])) {
// If a == b, only one permutation: (a, b, c)
// If a != b, two permutations: (a, b, c) and (b, a, c)
$count += ($a == $b) ? 1 : 2;
}
}
}
return $count;
}
// Test cases
echo countTriples(5) . "\n"; // Output: 2
echo countTriples(10) . "\n"; // Output: 4
?>Explanation:
|
Beta Was this translation helpful? Give feedback.
We are given n and need to count triples
(a, b, c)such thata² + b² = c², with1 <= 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: