Count Square Sum Triples - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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.
Approach 1: Brute Force Approach
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.
Complexity
Time Complexity: O(n^3)
Space Complexity: O(1)
Approach 2: Optimized Loop Approach
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.
Complexity
Time Complexity: O(n^2)
Space Complexity: O(1)
Approach 3: Enumeration
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).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3) |
| Optimized Loop Approach | Time Complexity: O(n^2) |
| Enumeration | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Count Square Sum Triples | Simple and Easy Solution | Leetcode 1925 | codestorywithMIK • codestorywithMIK • 4,161 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Count Square Sum Triples easy or hard?
Count Square Sum Triples Python/Java solution
How to solve Count Square Sum Triples in O(n²)?
What is the best approach for Count Square Sum Triples?
Is Count Square Sum Triples asked at Google/Amazon/Meta?
What data structure is used in Count Square Sum Triples?
What is the time complexity of Count Square Sum Triples?
Ready to solve this problem?
Practice Count Square Sum Triples with our built-in code editor and test cases.
Practice on FleetCode