LeetCode Entry

1925. Count Square Sum Triples

08.12.2025 easy 2025 kotlin rust

Count a^2+b^2=c^2 in 1..n range

1925. Count Square Sum Triples easy blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1197

Problem TLDR

Count a^2+b^2=c^2 in 1..n range #easy

Intuition

O(n^3) is accepted O(n^2): precompute n^2 numbers, lookup (a+b) in them

Approach

• we have to be in range 1..n, not in 1..250
• or check sqrt(aa+bb)

Complexity

• Time complexity: \(O(n^3)\) or O(n^2)

• Space complexity: \(O(n)\)

Code

// 49ms
    fun countTriples(n: Int): Int {
        val s = (1..n).map { it * it }.toSet()
        return s.sumOf { a-> s.count { b-> (a+b) in s}}
    }

// 5ms
    pub fn count_triples(n: i32) -> i32 {
        (1..=n).map(|a| 2*(a..=n).filter(|b| {
        let c = (a*a+b*b).isqrt(); c <= n && c*c==a*a+b*b}).count() as i32).sum::<i32>()
    }