LeetCode 1925. Count Square Sum Triples Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solution 1: Enumeration

We enumerate a and b in the range [1, n), then calculate c = √a² + b². If c is an integer and c ≤ n, then we have found a Pythagorean triplet, and we increment the answer by one.

After the enumeration is complete, return the answer.

The time complexity is O(n²), where n is the given integer. The space complexity is O(1).

PythonJavaC++GoTypeScript

class Solution: def countTriples(self, n: int) -> int: ans = 0 for a in range(1, n): for b in range(1, n): x = a * a + b * b c = int(sqrt(x)) if c <= n and c * c == x: ans += 1 return ans(code-box)

class Solution { public int countTriples(int n) { int ans = 0; for (int a = 1; a < n; a++) { for (int b = 1; b < n; b++) { int x = a * a + b * b; int c = (int) Math.sqrt(x); if (c <= n && c * c == x) { ans++; } } } return ans; } }(code-box)

class Solution { public: int countTriples(int n) { int ans = 0; for (int a = 1; a < n; ++a) { for (int b = 1; b < n; ++b) { int x = a * a + b * b; int c = static_cast<int>(sqrt(x)); if (c <= n && c * c == x) { ++ans; } } } return ans; } };(code-box)

func countTriples(n int) (ans int) { for a := 1; a < n; a++ { for b := 1; b < n; b++ { x := a*a + b*b c := int(math.Sqrt(float64(x))) if c <= n && c*c == x { ans++ } } } return }(code-box)

function countTriples(n: number): number { let ans = 0; for (let a = 1; a < n; a++) { for (let b = 1; b < n; b++) { const x = a * a + b * b; const c = Math.floor(Math.sqrt(x)); if (c <= n && c * c === x) { ans++; } } } return ans; }(code-box)