1925. Count Square Sum Triples
Description
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
Solutions
Solution 1: Enumeration
We enumerate $a$ and $b$ in the range $[1, n)$, then calculate $c = \sqrt{a^2 + b^2}$. If $c$ is an integer and $c \leq n$, then we have found a Pythagorean triplet, and we increment the answer by one.
After the enumeration is complete, return the answer.
The time complexity is $O(n^2)$, where $n$ is the given integer. The space complexity is $O(1)$.
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|