We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Square Sum Triples

Number: 2037

Difficulty: Easy

Paid? No

Companies: Qualtrics

Problem Description

Given an integer n, count the number of square triples (a, b, c) such that 1 <= a, b, c <= n and a² + b² = c². Note that different orderings of a and b count as distinct triples.

Key Insights

  • Use brute-force enumeration since n is small (n <= 250).
  • Iterate a and b in the range [1, n] and compute a² + b².
  • Check if the computed sum is a perfect square.
  • Ensure that the square root (c) is within the range [1, n].
  • Each valid triple (a, b, c) is counted separately even if a and b are swapped.

Space and Time Complexity

Time Complexity: O(n²) because of the nested iterations over a and b. Space Complexity: O(1) since only a few variables are used.

Solution

The solution involves iterating over all possible pairs (a, b) from 1 to n. For each pair, we calculate the sum of squares a² + b² and check if its square root is an integer using a square root function. If it is, and if the resulting c (the integer square root) is within the allowed range (1 to n), then we count that as a valid square triple. This approach uses double nested loops and basic arithmetic, making it both simple and effective for the given constraints.

Code Solutions

# Python solution for Count Square Sum Triples

import math

def countSquareSumTriples(n):
    count = 0
    # Iterate over possible values for a and b
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            c_squared = a * a + b * b  # Compute a^2 + b^2
            c = int(math.sqrt(c_squared))  # Get the integer part of the square root
            # Check if c is a valid integer square root and within range
            if c * c == c_squared and c <= n:
                count += 1
    return count

# Example usage:
print(countSquareSumTriples(5))  # Expected output: 2
print(countSquareSumTriples(10)) # Expected output: 4
← Back to All Questions