Jobs

Interviews

Discussions

Count Square Sum Triples

Easy

Asked by:

11 views

Topics:

Arrays

A square triple (a,b,c) is a triple where a, b, and c are integers and a² + b² = c².

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

Try coding it in LeetCode

Count Square Sum Triples

Easy

Asked by:

11 views

Topics:

Arrays

A square triple (a,b,c) is a triple where a, b, and c are integers and a² + b² = c².

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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the numbers in the input? Could the input contain negative numbers?
Is the input array sorted, or can it be in any order?
Are there any constraints on the size of the input array `n`?
If no square sum triples exist, what value should I return?
Are duplicate triples allowed? For instance, if `a^2 + b^2 = c^2` and `b^2 + a^2 = c^2`, should I count this as two triples or one?

Brute Force Solution

Approach

The brute force method for this problem involves checking every possible combination of three numbers to see if they form a square sum triple. We will try every combination and count the ones that fit the criteria.

Here's how the algorithm would work step-by-step:

Take the first number.
For that first number, try every possible second number.
For each combination of the first and second number, try every possible third number.
For each set of three numbers, check if the square of the first plus the square of the second equals the square of the third.
If the equation holds true, then we have found a valid square sum triple, so we increase our count.
Once we have gone through all combinations of the first, second, and third number, the final count will be our answer.

Code Implementation

def count_square_sum_triples(number_limit):
    count = 0

    for first_number in range(1, number_limit + 1):
        for second_number in range(1, number_limit + 1):
            # Test all possible values for the third number
            for third_number in range(1, number_limit + 1):

                # Check the equation to see if we found a triple
                if (first_number**2 + second_number**2) == third_number**2:
                    count += 1

    return count

Big(O) Analysis

Time Complexity

O(n^3) – The provided solution iterates through all possible combinations of three numbers from 1 to n. The first number is selected in a loop that goes from 1 to n. Nested within this loop is another loop to select the second number, which also goes from 1 to n. Finally, there's a third nested loop to select the third number, iterating from 1 to n. Since we have three nested loops, each dependent on n, the total number of operations is proportional to n * n * n, resulting in O(n^3) time complexity.

Space Complexity

O(1) – The brute force approach described involves iterating through all possible combinations of three numbers within the range [1, N]. The algorithm only uses a constant number of variables to store the loop counters and the count of valid triples. No auxiliary data structures, such as arrays or hash maps, are created. Therefore, the space complexity remains constant regardless of the input size N.

Optimal Solution

Approach

Instead of checking every possible combination of numbers to see if they form a square sum triple, we can use a more efficient method. We can precompute all the squares up to a certain limit and then quickly check if a combination satisfies the given condition using these precomputed squares.

Here's how the algorithm would work step-by-step:

First, calculate and store the squares of all the numbers from 1 up to the given input number.
Then, go through each number from 1 up to the input number and consider it as one side of the potential right triangle.
Next, for each of these numbers, check all other numbers (greater than the current number) to see if they could be the other side of the right triangle.
Use the precomputed squares to quickly determine if the sum of the squares of the two sides equals the square of any number within the original range.
If the sum of squares of two sides equals the square of another number, we have found a valid square sum triple, so count it.
By precalculating the squares, we avoid repeatedly calculating them, greatly speeding up the process.

Code Implementation

def count_square_sum_triples(number):
    squares = [i * i for i in range(1, number + 1)]
    count = 0

    # Iterate through possible 'a' values.
    for first_number in range(1, number + 1):
        for second_number in range(first_number + 1, number + 1):

            sum_of_squares = squares[first_number - 1] + squares[second_number - 1]

            # Check if sum_of_squares is a perfect square within range.
            if sum_of_squares in squares:
                third_number = int(sum_of_squares**0.5)

                # Ensure that the third number is within the given range.
                if third_number <= number:
                    count += 2

    return count

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through numbers from 1 to n, calculating the squares of each number to store in memory. Then, for each number 'a' from 1 to n, it checks all subsequent numbers 'b' (from a+1 to n) to find a third number 'c' where a² + b² = c². The outer loop runs n times, and the inner loop runs approximately n times on average. Therefore, the overall time complexity is dominated by the nested loops, resulting in approximately n * n/2 operations, which simplifies to O(n²).

Space Complexity

O(N) – The algorithm precomputes and stores the squares of all numbers from 1 up to the input number N. This is done to avoid repeated calculations, resulting in an auxiliary array of size N to store these squared values. Therefore, the space used grows linearly with the input N. The space complexity is O(N).

Edge Cases

Case	How to Handle
Input n is less than 3	Return 0 immediately, as no triples can exist with n < 3 because we need at least three numbers (a, b, c) where a,b,c > 0 and a < n, b < n, and c < n.
Input n is a large number	The algorithm iterates up to n, and the square calculation might cause integer overflow, so use a larger data type if needed.
No square sum triples exist for the given n	The algorithm should correctly return 0 in this scenario because the nested loops will complete without incrementing the count.
n is a negative number	Treat this as an invalid input and return 0, since the problem specifies positive integers for a, b, and c.
Integer overflow when calculating squares	Use a 64-bit integer data type (long or long long) to store the squares of a, b, and c to prevent overflow.
n is exactly 2	Return 0, as no triple can be formed from 1 and 2.
Extremely large n nearing the maximum integer value	Check for potential overflow during calculations and consider using libraries for arbitrary-precision arithmetic if required.
Duplicated square sum triples (e.g., a^2 + b^2 = c^2 and b^2 + a^2 = c^2)	Count only unique triples (a, b, c), where a < b, to avoid double-counting due to commutative property.

Input n is less than 3

How to Handle:

Return 0 immediately, as no triples can exist with n < 3 because we need at least three numbers (a, b, c) where a,b,c > 0 and a < n, b < n, and c < n.

Input n is a large number

How to Handle:

The algorithm iterates up to n, and the square calculation might cause integer overflow, so use a larger data type if needed.

No square sum triples exist for the given n

How to Handle:

The algorithm should correctly return 0 in this scenario because the nested loops will complete without incrementing the count.

n is a negative number

How to Handle:

Treat this as an invalid input and return 0, since the problem specifies positive integers for a, b, and c.

Integer overflow when calculating squares

How to Handle:

Use a 64-bit integer data type (long or long long) to store the squares of a, b, and c to prevent overflow.

n is exactly 2

How to Handle:

Return 0, as no triple can be formed from 1 and 2.

Extremely large n nearing the maximum integer value

How to Handle:

Check for potential overflow during calculations and consider using libraries for arbitrary-precision arithmetic if required.

Duplicated square sum triples (e.g., a^2 + b^2 = c^2 and b^2 + a^2 = c^2)

How to Handle:

Count only unique triples (a, b, c), where a < b, to avoid double-counting due to commutative property.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of the numbers in the input? Could the input contain negative numbers?
Is the input array sorted, or can it be in any order?
Are there any constraints on the size of the input array `n`?
If no square sum triples exist, what value should I return?
Are duplicate triples allowed? For instance, if `a^2 + b^2 = c^2` and `b^2 + a^2 = c^2`, should I count this as two triples or one?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number.
For that first number, try every possible second number.
For each combination of the first and second number, try every possible third number.
For each set of three numbers, check if the square of the first plus the square of the second equals the square of the third.
If the equation holds true, then we have found a valid square sum triple, so we increase our count.
Once we have gone through all combinations of the first, second, and third number, the final count will be our answer.

Code Implementation

def count_square_sum_triples(number_limit):
    count = 0

    for first_number in range(1, number_limit + 1):
        for second_number in range(1, number_limit + 1):
            # Test all possible values for the third number
            for third_number in range(1, number_limit + 1):

                # Check the equation to see if we found a triple
                if (first_number**2 + second_number**2) == third_number**2:
                    count += 1

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate and store the squares of all the numbers from 1 up to the given input number.
Then, go through each number from 1 up to the input number and consider it as one side of the potential right triangle.
Next, for each of these numbers, check all other numbers (greater than the current number) to see if they could be the other side of the right triangle.
Use the precomputed squares to quickly determine if the sum of the squares of the two sides equals the square of any number within the original range.
If the sum of squares of two sides equals the square of another number, we have found a valid square sum triple, so count it.
By precalculating the squares, we avoid repeatedly calculating them, greatly speeding up the process.

Code Implementation

def count_square_sum_triples(number):
    squares = [i * i for i in range(1, number + 1)]
    count = 0

    # Iterate through possible 'a' values.
    for first_number in range(1, number + 1):
        for second_number in range(first_number + 1, number + 1):

            sum_of_squares = squares[first_number - 1] + squares[second_number - 1]

            # Check if sum_of_squares is a perfect square within range.
            if sum_of_squares in squares:
                third_number = int(sum_of_squares**0.5)

                # Ensure that the third number is within the given range.
                if third_number <= number:
                    count += 2

    return count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n is less than 3	Return 0 immediately, as no triples can exist with n < 3 because we need at least three numbers (a, b, c) where a,b,c > 0 and a < n, b < n, and c < n.
Input n is a large number	The algorithm iterates up to n, and the square calculation might cause integer overflow, so use a larger data type if needed.
No square sum triples exist for the given n	The algorithm should correctly return 0 in this scenario because the nested loops will complete without incrementing the count.
n is a negative number	Treat this as an invalid input and return 0, since the problem specifies positive integers for a, b, and c.
Integer overflow when calculating squares	Use a 64-bit integer data type (long or long long) to store the squares of a, b, and c to prevent overflow.
n is exactly 2	Return 0, as no triple can be formed from 1 and 2.
Extremely large n nearing the maximum integer value	Check for potential overflow during calculations and consider using libraries for arbitrary-precision arithmetic if required.
Duplicated square sum triples (e.g., a^2 + b^2 = c^2 and b^2 + a^2 = c^2)	Count only unique triples (a, b, c), where a < b, to avoid double-counting due to commutative property.

Input n is less than 3

How to Handle:

Return 0 immediately, as no triples can exist with n < 3 because we need at least three numbers (a, b, c) where a,b,c > 0 and a < n, b < n, and c < n.

Input n is a large number

How to Handle:

The algorithm iterates up to n, and the square calculation might cause integer overflow, so use a larger data type if needed.

No square sum triples exist for the given n

How to Handle:

The algorithm should correctly return 0 in this scenario because the nested loops will complete without incrementing the count.

n is a negative number

How to Handle:

Treat this as an invalid input and return 0, since the problem specifies positive integers for a, b, and c.

Integer overflow when calculating squares

How to Handle:

Use a 64-bit integer data type (long or long long) to store the squares of a, b, and c to prevent overflow.

n is exactly 2

How to Handle:

Return 0, as no triple can be formed from 1 and 2.

Extremely large n nearing the maximum integer value

How to Handle:

Check for potential overflow during calculations and consider using libraries for arbitrary-precision arithmetic if required.

Duplicated square sum triples (e.g., a^2 + b^2 = c^2 and b^2 + a^2 = c^2)

How to Handle:

Count only unique triples (a, b, c), where a < b, to avoid double-counting due to commutative property.