Count Square Sum Triples - Leetcode Solution

Problem Statement:

Given an integer n, return the number of triplets (i, j, k) with 1 ≤ i < j < k ≤ n such that i² + j² = k².

Solution:

To find the number of triplets (i, j, k), we need to iterate through all possible combinations of i, j, and k from 1 to n, where i < j < k. The condition we need to check for each combination is whether i² + j² is equal to k², and if it is, increment the count.

We can optimize this by recognizing that for a given value of i, there are only a certain number of values for j and k that could potentially satisfy the condition i² + j² = k². Specifically, we can calculate the maximum value of j, given i, as √(n² - i²). This is because k can be at most n, and we want j < k, so k² will be greater than i², which leaves a maximum value of n² - i² for the square of j. We can then iterate through all values of j from i+1 up to the maximum value we just calculated, and check whether there exists a value for k that satisfies the condition i² + j² = k².

If we find a valid k for a given i and j, we can increment the count and move on to the next value of j. If we finish iterating through all values of j for a given i without finding any valid k values, we can move on to the next value of i.

Here is the code to implement this solution:

class Solution { public: int countTriples(int n) { int count = 0; for (int i = 1; i <= n; i++) { int max_j = sqrt(nn - ii); for (int j = i + 1; j <= max_j; j++) { int k_squared = ii + jj; int k = sqrt(k_squared); if (k*k == k_squared && k <= n) { count++; } } } return count; } };

Time Complexity:

The outer loop runs for n iterations, and for each iteration, the inner loop runs for at most √(n² - i²) iterations, so the time complexity of this solution is O(n √n).

Space Complexity:

This solution uses only a constant amount of extra space, so the space complexity is O(1).

1