Skip to content

2037. Count Square Sum Triples

Math Enumeration

Problem - Count Square Sum Triples

Easy

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def countTriples(self, n: int) -> int:
        # result = 0
        # for a in range(1, n):
        #     for b in range(1, n):
        #         val = a**2 + b**2
        #         c = int(sqrt(val))
        #         if c <= n and val == c**2:
        #             result += 1
        # return result

        result = 0
        squares = set([i**2 for i in range(1, n + 1)])
        for a in range(1, n + 1):
            for b in range(a + 1, n + 1):
                if a**2 + b**2 in squares:
                    result += 2
        return result

Submission Stats:

  • Runtime: 87 ms (86.69%)
  • Memory: 17.7 MB (54.08%)