A bridge-maintenance crew keeps an inventory of steel braces whose lengths are the integers 1 through n (any length may be reused in a different slot). A support is considered stable if two braces of lengths x and y form the two legs meeting at a right angle, and a third brace of length z forms the diagonal, satisfying x^2 + y^2 = z^2. Because the two leg slots in a support are mounted in different orientations -- one horizontal, one vertical -- a configuration using leg lengths (x, y) is treated as different from one using (y, x) whenever x != y; both are valid, distinct configurations.
Given n, count the number of ordered triples (x, y, z) with 1 <= x, y, z <= n satisfying x^2 + y^2 = z^2.
A single line containing one integer n.
Print a single integer: the number of ordered triples (x, y, z) with 1 <= x, y, z <= n and x^2 + y^2 = z^2.
Example 1
Input
5
Expected
2
Explanation
With lengths limited to 1..5, the only right-triangle relation is 3^2+4^2=5^2. Both leg orderings (3,4,5) and (4,3,5) are valid distinct configurations, and no other combination of x,y,z up to 5 works, so the count is 2.
Example 2
Input
10
Expected
4
Explanation
Up to length 10, the qualifying triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10) -- the 3-4-5 triple and its double, each counted in both leg orderings. No other triple with z<=10 satisfies the relation, so the count is 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →