Count Square Sum Triples Solution in Java

Problem Description

Welcome to the whimsical world of counting square sum triples! Imagine you’re at a party, and everyone is trying to find their perfect match. But instead of swiping right, you’re looking for three numbers a, b, and c such that a2 + b2 = c2. Sounds like a math party gone wild, right?

In this problem, you need to count how many such triples exist for numbers from 1 to n. So, if you’re thinking about how many ways you can form a Pythagorean triplet with numbers up to n, you’re in the right place!

Code Solution


class Solution {
  public int countTriples(int n) {
    int ans = 0;
    Set squared = new HashSet<>();

    for (int i = 1; i <= n; ++i)
      squared.add(i * i);

    for (final int a : squared)
      for (final int b : squared)
        if (squared.contains(a + b))
          ++ans;

    return ans;
  }
}

Approach

The approach here is as straightforward as counting your friends at a party. First, we create a set of squares for all numbers from 1 to n. Then, we check every combination of these squares to see if their sum is also a square in our set. If it is, we increment our count. It’s like finding the perfect dance partners for a square dance!

Time and Space Complexity

Time Complexity: O(n2) - We iterate through all pairs of squares, which gives us a quadratic time complexity.

Space Complexity: O(n) - We store the squares in a set, which takes linear space.

Real-World Example

Imagine you’re trying to find the best trio of friends to form a band. Each friend has a unique talent (like a number), and you want to see if their combined talents can create a harmonious sound (like a perfect square). The Count Square Sum Triples problem is just like that! You’re counting how many unique combinations of talents can create that perfect harmony.

Similar Problems

3 Sum Solution in Java