Leetcode 1925: Count Square Sum Triples

Input: You are given a single integer n.

Example: n = 6

Constraints:

• 1 <= n <= 250

Output: Return the number of square triples (a, b, c) where 1 <= a, b, c <= n and a^2 + b^2 = c^2.

Example: 2

Constraints:

Goal: Find pairs (a, b) where a^2 + b^2 = c^2 and check if c is within the range of 1 to n.

Steps:

• Iterate through all pairs (a, b) where 1 <= a, b <= n.

• For each pair, compute a^2 + b^2.

• Check if the result is a perfect square and if the corresponding c value is within the range 1 to n.

• Count such pairs where the condition holds.

Goal: Ensure that the solution handles the constraints efficiently, especially given that n can be as large as 250.

Steps:

• The input integer n will always be between 1 and 250.

• You must count all distinct triples (a, b, c) where the order matters.

Assumptions:

• The problem assumes that n is always positive and within the given range.

• The solution should be able to handle the maximum value of n efficiently.

• Input: n = 6

• Explanation: For n = 6, the valid square triples are (3, 4, 5) and (4, 3, 5), which gives the output 2.

Approach: The approach is to iterate through all possible pairs (a, b) and check if the sum of their squares is a perfect square. If it is, check if the resulting c value lies within the range of 1 to n.

Observations:

• We need to efficiently check if a^2 + b^2 is a perfect square.

• The solution needs to check for all pairs (a, b), and for each pair, verify if c^2 exists in the range of 1 to n. This involves calculating squares and checking for perfect squares.

Steps:

• Loop over all possible values for a and b from 1 to n.

• For each pair, compute a^2 + b^2.

• Check if the sum is a perfect square by taking the square root and comparing the squared result.

• Ensure that the value of c is within the valid range and count such triples.

Empty Inputs:

• The input n will always be positive, so no empty inputs will occur.

Large Inputs:

• Since n can be as large as 250, ensure the solution is efficient enough to handle the maximum input size.

Special Values:

• The smallest valid input is n = 1, which will have no valid square triples.

Constraints:

• Ensure the algorithm efficiently handles up to 250 iterations for n.

int countTriples(int n) {
vector<bool> squares(n * n + 1);
for (int i = 1; i <= n; ++i)
    squares[i * i] = true;
int res = 0;
for (int i = 1; i <= n; ++i)
    for (int j = i; i * i + j * j <= n * n; ++j)
        res += squares[i * i + j * j] * 2;
return res;
}

1 : Function Definition

int countTriples(int n) {

Defines the function 'countTriples' that takes an integer 'n' as input and returns the count of valid Pythagorean triples less than or equal to 'n'.

2 : Array Initialization

vector<bool> squares(n * n + 1);

Initializes a vector 'squares' of size 'n * n + 1' to store boolean values, where each index represents whether the index is a perfect square.

3 : Loop Start

for (int i = 1; i <= n; ++i)

Begins a loop to iterate over integers 'i' from 1 to 'n' to mark squares in the 'squares' vector.

4 : Square Marking

    squares[i * i] = true;

Marks 'squares[i * i]' as true to indicate that 'i * i' is a perfect square.

5 : Variable Initialization

int res = 0;

Initializes the result variable 'res' to 0, which will store the number of valid Pythagorean triples.

6 : Outer Loop Start

for (int i = 1; i <= n; ++i)

Begins the outer loop over integer 'i' to iterate through possible sides of the Pythagorean triple.

7 : Inner Loop Start

    for (int j = i; i * i + j * j <= n * n; ++j)

Begins the inner loop with integer 'j' starting from 'i' to ensure 'i <= j' and continues while 'i * i + j * j' is less than or equal to 'n * n'.

8 : Count Triples

        res += squares[i * i + j * j] * 2;

Checks if 'i * i + j * j' is a perfect square by looking up its value in the 'squares' vector. If it is, it increments 'res' by 2 (accounting for both (i, j) and (j, i) pairs).

9 : Return

return res;

Returns the final count of Pythagorean triples.

Best Case: O(n^2)

Average Case: O(n^2)

Worst Case: O(n^2)

Description: The time complexity is O(n^2) due to the two nested loops that iterate over all pairs (a, b).

Best Case: O(1)

Worst Case: O(1)

Description: The space complexity is O(1) since we only need a few variables to store intermediate results.

Leetcode 1925: Count Square Sum Triples

Explore →