Scale Engineer

Count Square Sum Triples

Easy
#1756Time: 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.1 company
Patterns
MathEnumeration
Companies
Qualtrics

Prompt

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 count to 0.
  • Use three nested loops to iterate a, b, and c from 1 to n.
  • 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 for loops. The outer loop iterates a from 1 to n, the middle loop iterates b from 1 to n, and the inner loop iterates c from 1 to n.
  • Inside the innermost loop, we compute a*a + b*b and compare it with c*c.
  • If a*a + b*b == c*c, we have found a valid square triple, and we increment our count.
  • After all possible combinations have been checked, the final value of count is 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.

Solutions

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;  }}

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.

← Previous

Previous problem

Next →

Next problem