Question

Approach

I iterate over all ordered pairs (a,b) with 1 ≤ a,b ≤ n and compute s = aa + bb. I take the integer square root c = isqrt(s) and check whether c*c == s and c ≤ n. If so, (a,b,c) is a valid square triple — I count it.

Implementation

class Solution:
    def countTriples(self, n: int) -> int:
        ans = 0
        for a in range(1, n + 1):
            for b in range(1, n + 1):
                s = a*a + b*b
                c = math.isqrt(s)
                if c*c == s and c <= n:
                    ans += 1
        return ans

Complexities

• Time: O(n^2)
• Space: O(1)