## Similar Problems

Similar Problems not available

# Count Square Sum Triples - Leetcode Solution

## Companies:

LeetCode: Count Square Sum Triples Leetcode Solution

Difficulty: Easy

Topics: math

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(n*n - i*i);
for (int j = i + 1; j <= max_j; j++) {
int k_squared = i*i + j*j;
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).

## Count Square Sum Triples Solution Code

`1`