1066. Square Triples
A tiler cuts square tiles with whole-number side lengths. Two small square tiles of sides a and b can be replaced by one big square tile of side c exactly when the areas match, that is a*a + b*b == c*c. The biggest tile available has side n, so c may not exceed n.
Count the ordered triples (a, b, c) of positive integers with a*a + b*b == c*c and c <= n. The triples (a, b, c) and (b, a, c) are counted separately whenever a != b. A double loop over a and b with an exact integer square-root test is enough: O(n^2) time and O(1) space.
Example 1
- Input:
- n = 13
- Output:
- 6
- Explanation:
The triples (3,4,5), (6,8,10) and (5,12,13) each appear in both orders, giving 6.
Example 2
- Input:
- n = 25
- Output:
- 16
- Explanation:
Besides the 13-limit triples, (9,12,15), (8,15,17), (12,16,20), (15,20,25) and (7,24,25) also fit, and each is counted in both orders.
Constraints
1 ≤ n ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n^2)
- Space
- O(1)