carloscn / structstudy

Leetcode daily trainning by using C/C++/RUST programming.
4 stars 1 forks source link

leetcode1925: Count Square Sum Triples #308

Open carloscn opened 1 year ago

carloscn commented 1 year ago

Description

A square triple (a,b,c) is a triple where a, b, and c are integers and a2 + b2 = c2.

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

Example 1:

Input: n = 5 Output: 2 Explanation: The square triples are (3,4,5) and (4,3,5).

Example 2:

Input: n = 10 Output: 4 Explanation: The square triples are (3,4,5), (4,3,5), (6,8,10), and (8,6,10).

Constraints:

1 <= n <= 250

carloscn commented 1 year ago

Analysis

// 1 2 3 4 5 6 7 8 9 10

// 1 2 10 / 1 2 9 / 1 2 8 / 1 2 7 / 1 2 6 / 1 2 5 / 1 2 4 / 1 2 3
// 1 3 10 / 1 3 9 / ... / 1 3 4
// 1 4 10 / 1 4 9 / ... / 1 4 5
// 2 3 10 / 2 3 9
// ...
// ...

pub fn count_triples(n: i32) -> i32
{
    if n < 3 {
        return 0;
    }

    let mut ret:i32 = 0;

    for i in 1..n + 1 {
        for j in (i + 1)..n + 1 {
            for k in (j + 1)..n + 1{
                if  i * i + j * j == k * k {
                    ret += 2;
                }
            }
        }
    }

    return ret;
}
carloscn commented 1 year ago

Code

https://review.gerrithub.io/c/carloscn/structstudy/+/1167585 https://github.com/carloscn/structstudy/commit/1266e2bd6d2129e21a6a3af5aa264b55cff4c32f