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 <= 250Problem Overview: Given an integer n, count the number of ordered triples (a, b, c) such that 1 ≤ a, b, c ≤ n and a² + b² = c². The task is essentially finding all Pythagorean triples within the range [1, n].
Approach 1: Brute Force Enumeration (O(n³) time, O(1) space)
Iterate over every possible combination of a, b, and c from 1 to n. For each triple, compute a*a + b*b and compare it with c*c. If they match, increment the count. This method directly checks the Pythagorean condition without any optimization. It’s useful for understanding the problem constraints and validating smaller inputs, but the cubic time complexity becomes expensive as n grows.
Approach 2: Optimized Loop with Square Root Check (O(n²) time, O(1) space)
Instead of iterating over all three variables, iterate only over a and b. Compute sum = a*a + b*b and check whether it forms a perfect square. If c = sqrt(sum) is an integer and c ≤ n, a valid triple exists. This removes the third loop and reduces the complexity to quadratic. The key insight is treating c as a derived value rather than iterating through all candidates. This approach relies on basic math properties and systematic enumeration of pairs.
Recommended for interviews: Start by describing the brute force enumeration to show you understand the constraint a² + b² = c². Then move to the optimized two-loop approach that computes c using a square root check. Interviewers typically expect the O(n²) solution because it removes unnecessary iteration while keeping the implementation simple.
The brute force approach involves iterating through all possible values of a, b, and c within the range of 1 to n and checking if they satisfy the condition a^2 + b^2 = c^2.
This solution uses three nested loops to iterate over all values of a, b, and c from 1 to n. It checks if the sum of the squares of a and b equals the square of c. If a valid triple is found, the count is incremented. The result is the number of such valid triples.
Time Complexity: O(n^3)
Space Complexity: O(1)
By noticing that c will always be larger than or equal to both a and b in a Pythagorean triple, we can optimize by directly iterating a and b with the constraint that their sum of squares should exactly form a square of another integer c.
This optimized C solution uses only two nested loops over a and b, calculating c using the square root of a^2 + b^2. If c is an integer and within bounds, it counts both (a, b, c) and (b, a, c) as valid triples due to symmetry, thus incrementing count by 2.
Time Complexity: O(n^2)
Space Complexity: O(1)
We enumerate a and b in the range [1, n), then calculate c = \sqrt{a^2 + b^2}. If c is an integer and c leq 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^2), where n is the given integer. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) |
| Optimized Loop Approach | Time Complexity: O(n^2) |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n³) | O(1) | When demonstrating the direct definition of the problem or validating small constraints |
| Optimized Loop with Square Root Check | O(n²) | O(1) | Preferred approach for interviews and production due to reduced iteration |
Count Square Sum Triples | Simple and Easy Solution | Leetcode 1925 | codestorywithMIK • codestorywithMIK • 4,102 views views
Watch 9 more video solutions →Practice Count Square Sum Triples with our built-in code editor and test cases.
Practice on FleetCode