Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Once the two positive legs are chosen, the only possible third value is the square root of their squared sum. Checking that it is an integer avoids an additional loop. Swapping unequal legs gives a distinct ordered triple with the same third value.

Approach

Enumerate a < b between one and n. Compute the integer part of sqrt(a*a + b*b), then verify its square equals the original sum and that it does not exceed n. Add two for each match, counting both leg orders. Equal positive legs cannot produce an integer hypotenuse, so excluding them loses no solutions. Return the total.

class Solution:
    def countTriples(self, n: int) -> int:
        res = 0

        for i in range(1, n + 1):
            for j in range(i + 1, n + 1):
                # for k in range(j + 1, n + 1):
                    # if i**2 + j**2 == k**2:
                        # res += 2
                k = int(sqrt(i**2 + j**2))
                if k <= n and i**2 + j**2 == k**2:
                    res += 2

        return res

Complexity analysis

Time: O(n^2) for all ordered choices with a < b; each square-root/integer check is constant time for the constrained numeric range. Auxiliary space: O(1).