algoadvance

Leetcode 1925. Count Square Sum Triples

Problem Statement

  1. Count Square Sum Triples

Given an integer n, return the number of square sum triples such that 1 <= a, b, c <= n and a^2 + b^2 = c^2.

A square sum triple (a,b,c) is a set of three positive integers that satisfy the above condition.

Clarifying Questions

  1. Input Constraints:
    • What is the range of n? (Typically, knowing the constraints can help in optimizing the solution if required.)
    • Are a, b, and c distinct?
  2. Output:
    • The output should be a single integer representing the number of square sum triples.

Let’s assume n can be moderately large based on typical problem constraints (e.g., 1 ≤ n ≤ 250 according to Leetcode standard constraints). Moreover, a, b, and c are distinct positive integers constrained by the range [1, n].

Strategy

  1. Iterate Over Possible Values:
    • We need to consider all possible triples (a, b, c) where 1 <= a, b, c <= n.
    • Check if a^2 + b^2 == c^2.
  2. Loop Structure:
    • Use nested loops to generate all possible values of a and b.
    • For each pair (a, b), compute c = sqrt(a^2 + b^2).
    • Check if c is an integer and within the range [1, n].

Time Complexity

Code

#include <iostream>
#include <cmath>   // for sqrt
using namespace std;

class Solution {
public:
    int countSquareSumTriples(int n) {
        int count = 0;
        
        for (int a = 1; a <= n; ++a) {
            for (int b = 1; b <= n; ++b) {
                int cSquared = a * a + b * b;
                int c = sqrt(cSquared);
                if (c <= n && c * c == cSquared) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

int main() {
    Solution solution;
    int n = 10; // Example input
    int result = solution.countSquareSumTriples(n);
    cout << "Number of square sum triples: " << result << endl;
    return 0;
}

Time Complexity Analysis

Hence, the overall time complexity is O(n^2 * sqrt(n)) due to the computational cost and validation within the nested loops.

This solution explores all combinations and checks the conditions efficiently within polynomial time complexity constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI