Count Square Sum Triples - Video Solutions

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.