algoadvance

Leetcode 1925. Count Square Sum Triples

Problem Statement:

Given a positive integer n, you need to return the number of triplets (a, b, c) such that:

  1. 1 <= a, b, c <= n
  2. a^2 + b^2 = c^2

Clarifying Questions:

  1. Should the triplets (a, b, c) be unique, meaning (a, b, c) is considered the same as (b, a, c)?
    • Typically, in most problems the order of (a, b) doesn’t matter unless otherwise stated.
  2. Do a, b, and c need to be distinct?
    • Based on the typical phrasing of such problems, a and b are usually allowed to be the same, but we should confirm to avoid ambiguity.

Strategy:

To solve the problem, we can iterate through all possible values of a and b within the range [1, n], and then check if c = sqrt(a^2 + b^2) (where c also needs to be an integer and within the range). If c falls within the range [1, n], then (a, b, c) is a valid triplet.

Code:

Here is a possible implementation in Java:

public class Solution {
    public int countTriples(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 = (int) Math.sqrt(cSquared);
                // Check if c is an integer and within the range [1, n]
                if (c <= n && c * c == cSquared) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

Strategy Explanation:

  1. Iteration through Possible a and b:
    • Use nested loops to iterate over all pairs (a, b) such that both a and b lie within [1, n].
  2. Square Sum Calculation and Verification:
    • Calculate cSquared as a^2 + b^2.
    • Compute c as the integer square root of cSquared.
    • Verify if c squared is equal to cSquared and if c lies within [1, n].
    • If these conditions are met, increment the count.

Time Complexity:

  1. Nested Loop Complexity:
    • The time complexity of the nested loops (for a and b) is O(n^2).
  2. Square Root Calculation:
    • Math.sqrt is O(1) since it operates in constant time.
  3. Final Complexity:
    • Overall, the solution runs in O(n^2) time.

This solution is efficient enough for the given constraints of the problem.

Would you like us to explore any other aspects or optimize further?

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