Count Square Sum Triples Solution in Python

Problem Description

Welcome to the world of counting square sum triples! Imagine you’re at a party, and everyone is trying to impress each other with their math skills. The challenge? Find all unique triples of integers (a, b, c) such that a² + b² = c² and all integers are less than or equal to a given number n.

Now, if you think this is just a math problem, think again! It’s like trying to find the perfect combination of ingredients for a cake, but instead of flour and sugar, you’re mixing squares of numbers. And just like baking, if you get the wrong combination, you might end up with a flat cake—or in this case, no valid triples!

Code Solution

class Solution:
    def countTriples(self, n: int) -> int:
        ans = 0
        squared = set()

        for i in range(1, n + 1):
            squared.add(i * i)

        for a in squared:
            for b in squared:
                if a + b in squared:
                    ans += 1

        return ans
    

Approach Explanation

The approach here is as straightforward as counting your fingers. First, we create a set of squares for all integers 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 answer. It’s like playing a game of matchmaker, but instead of finding love, we’re finding numbers that fit together perfectly!

Time and Space Complexity

Time Complexity: O(n²) – We have two nested loops iterating through the squared set.

Space Complexity: O(n) – We store the squares of numbers in a set.

Real-World Example

Imagine you’re trying to build a triangular pyramid with blocks. Each block represents a number, and you can only use blocks that are perfect squares. You want to know how many unique ways you can stack these blocks to form a perfect triangle. This problem is just like that! You’re counting the unique combinations of blocks (or numbers) that can form a perfect triangle (or satisfy the equation a² + b² = c²).