Count Square Sum Triples
EasyPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most straightforward but least efficient approach. It involves using three nested loops to iterate through all possible combinations of integers a, b, and c from 1 to n. For each combination, it checks if they form a square triple by verifying the equation a^2 + b^2 = c^2.
Algorithm
- Initialize a counter
countto 0. - Use three nested loops to iterate
a,b, andcfrom 1 ton. - Inside the innermost loop, check if
a*a + b*b == c*c. - If the condition is true, increment
count. - After the loops complete, return
count.
Walkthrough
The algorithm systematically checks every single possible triple (a, b, c) where each element is between 1 and n.
- We initialize a counter variable,
count, to zero. - We set up three nested
forloops. The outer loop iteratesafrom 1 ton, the middle loop iteratesbfrom 1 ton, and the inner loop iteratescfrom 1 ton. - Inside the innermost loop, we compute
a*a + b*band compare it withc*c. - If
a*a + b*b == c*c, we have found a valid square triple, and we increment ourcount. - After all possible combinations have been checked, the final value of
countis the answer.
class Solution { public int countTriples(int n) { int count = 0; for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { for (int c = 1; c <= n; c++) { if (a * a + b * b == c * c) { count++; } } } } return count; }}Complexity
Time
O(n^3) - There are three nested loops, and each loop runs up to `n` times, leading to a cubic time complexity.
Space
O(1) - We only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Very simple to understand and implement.
Requires no extra space besides a few variables.
Cons
Highly inefficient due to its cubic time complexity.
Will be very slow or time out for larger values of
n.
This approach improves upon the brute-force method by eliminating the third loop for c. It iterates through all pairs of a and b and then calculates the required value of c. It then checks if this calculated c is an integer and falls within the valid range [1, n].
Algorithm
- Initialize a counter
countto 0. - Use two nested loops to iterate
aandbfrom 1 ton. - For each pair
(a, b), calculatesum_sq = a*a + b*b. - Calculate
c = sqrt(sum_sq). - Check if
cis an integer (by verifyingc*c == sum_sq) and ifc <= n. - If both conditions are met, increment
count. - Return
count.
Walkthrough
Instead of iterating through c, we can derive it from a and b. This reduces the complexity from cubic to quadratic.
- We iterate through all possible values for
aandbfrom 1 tonusing two nested loops. - For each pair
(a, b), we calculate the sum of their squares:sumSq = a*a + b*b. - We then find the potential value of
cby taking the square root ofsumSq. - To ensure
cis a valid integer, we can cast the result of the square root to an integer and then check if its square equalssumSq. For example,int c = (int) Math.sqrt(sumSq);and then checkc*c == sumSq. - We also must verify that this integer
cis within the allowed range, i.e.,c <= n. - If both conditions are met, we've found a valid triple, and we increment our counter.
class Solution { public int countTriples(int n) { int count = 0; for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { int sumSq = a * a + b * b; int c = (int) Math.sqrt(sumSq); if (c * c == sumSq && c <= n) { count++; } } } return count; }}Complexity
Time
O(n^2) - We use two nested loops, each running up to `n` times. The operations inside the loops, including `Math.sqrt`, are considered to take constant time.
Space
O(1) - No auxiliary data structures are needed; only a few variables are used for storage.
Trade-offs
Pros
Significantly more efficient than the O(n^3) approach.
Maintains O(1) space complexity.
Still relatively easy to understand and implement.
Cons
Involves floating-point arithmetic (
Math.sqrt), which can be slightly slower than pure integer operations.
This approach further optimizes the two-loop method by avoiding repeated square root calculations. It pre-computes all perfect squares up to n*n and stores them in a hash set. This allows for a constant-time lookup to check if a^2 + b^2 is a perfect square within the required range.
Algorithm
- Create a
HashSetnamedsquares. - Loop
ifrom 1 tonand addi*ito thesquaresset. - Initialize
count = 0. - Loop
afrom 1 ton. - Loop
bfrom 1 ton. -
Calculate `sum_sq = a*a + b*b`. -
Check if `sum_sq` exists in the `squares` set. -
If it does, increment `count`. - Return
count.
Walkthrough
This method trades space for time. By pre-calculating values, we can make the check inside the loops faster.
- First, we create a
HashSetto store the squares of all integers from 1 ton. We iterate fromi = 1tonand addi*ito the set. This gives us a collection of all possiblec*cvalues wherec <= n. - Next, we use two nested loops to iterate through
afrom 1 tonandbfrom 1 ton. - Inside the inner loop, we calculate
sumSq = a*a + b*b. - Instead of using
Math.sqrt, we simply check ifsumSqis present in ourHashSet. A successful lookup means there exists an integercsuch thatc*c = sumSqandc <= n. - If
sumSqis found in the set, we increment our counter. - This approach is generally faster in practice as hash set lookups are very efficient and it avoids floating-point arithmetic.
import java.util.HashSet;import java.util.Set; class Solution { public int countTriples(int n) { Set<Integer> squares = new HashSet<>(); for (int i = 1; i <= n; i++) { squares.add(i * i); } int count = 0; for (int a = 1; a <= n; a++) { for (int b = 1; b <= n; b++) { int sumSq = a * a + b * b; if (squares.contains(sumSq)) { count++; } } } return count; }}Complexity
Time
O(n^2) - The pre-computation step takes `O(n)`. The main part consists of two nested loops running in `O(n^2)`, with each hash set lookup taking `O(1)` on average. The total complexity is dominated by the nested loops.
Space
O(n) - We need to store `n` perfect squares in the hash set.
Trade-offs
Pros
Very efficient for the given constraints, often faster in practice than the
sqrtmethod.Avoids floating-point arithmetic, which can prevent potential precision issues.
Cons
Uses extra space to store the set of squares, which is a time-space tradeoff.
Solutions
Solution
class Solution {public int countTriples(int n) { int res = 0; for (int a = 1; a <= n; ++a) { for (int b = 1; b <= n; ++b) { int t = a * a + b * b; int c = (int)Math.sqrt(t); if (c <= n && c * c == t) { ++res; } } } return res; }}class Solution: def countTriples(self, n: int) -> int: res = 0 for a in range(1, n + 1): for b in range(1, n + 1): t = a ** 2 + b ** 2 c = int(sqrt(t)) if c <= n and c ** 2 == t: res += 1 return resclass Solution {public: int countTriples(int n) { int res = 0; for (int a = 1; a <= n; ++a) { for (int b = 1; b <= n; ++b) { int t = a * a + b * b; int c = (int)sqrt(t); if (c <= n && c * c == t) { ++res; } } } return res; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.