006. Sum Square Difference ("제곱의 합"과 "합의 제곱"과의 차 구하기)

 

 

​문제 (English)

The sum of the squares of the first ten natural number is,

$1^2 + 2^2 + ...+10^2 = 385$

The square of the sum of the first ten natural number is,

$(1+2+...+10)^2 = 55^2 = 3025 $

Hence the difference between the sum of the squares of the first ten natural numbers and the sqrare of the sum is $3025-385=2640$.

Fine the difference between the sum of the squares of the first one hundread natural numbers and the square ot the sum.

 

Answer: 25164150

문제 분석

---

제곱의 합과, 합의 제곱의 차를 구하는 문제.

 

합공식을 알고 있다면 쉽게 풀수 있는 문제이다.

 

1에서 n까지의 합 S는,

$ S = 1+2+...+n =  \frac {n(n+1)}{2}$

 

제곱의 합은,

$S = 1^2 + 2^2 +..._+n^2 = \frac {n(n+1)(2n+1)}{6}$

풀이 1 

---

단순 합 공식은 알고 있어서 공식으로 풀고, 제곱의 합의 그냥 루프를 돌려서 풀어 본다.

#[test]
fn test(){
    assert_eq!(0, answer(1));
    assert_eq!(4, answer(2));
    assert_eq!(22, answer(3));
    assert_eq!(2640, answer(10));
    assert_eq!(25164150, answer(100));    
}

#[cfg(test)]
//(1+...+100)^2 - (1^2 + ... +100^2)
// (100*101/2)^2 - ( ... )
fn answer(n: u64) -> u64{
    //1. a = (1+...+100)^2
    let mut a: u64 = get_seq_sum(n);
    a = a.pow(2);

    //2. b = (1^2 + ... +100^2)
    let b: u64 = get_square_sum(n);

    //3. a-b
    a - b    
}

#[cfg(test)]
fn get_seq_sum(n: u64) -> u64{
    n * (n+1) / 2
}

#[cfg(test)]
fn get_square_sum(n: u64) -> u64{
    let mut sum: u64 = 0;

    for i in 1..=n {
        sum += i.pow(2);
    }
    return sum;
}

 

이렇게 해도 hackerrank 통과한다.

풀이 2 

---

제곱수에 대한 합도 공식을 이용해서 푼다.

 

fn get_square_sum1(n: u64) -> u64{
    n*(n+1)*(2*n+1)/6
}

 

총평

---

u32말고 u64로 사용하고, 공식만을 알면 쉽게 풀 수 있는 문제

 

전체 소스코드

---

p6.rs 

/// - 공식을 사용해서 계산하는 것이 제일 빠르다. 
///   1)연속된 자연수의 합 공식
///   2)연속된 자연수제곱의 합 공식
/// - 그 다음은 그냥 원시적으로 루프에 의해서 계산하는 것
/// - (a+b)^2 = a^2 + b^2 -2ab를 이용해서 푸는 것은, 오히려 계산량이 더 많다.
/// 

#[test]
fn test(){
    assert_eq!(0, answer(1));
    assert_eq!(4, answer(2));
    assert_eq!(22, answer(3));
    assert_eq!(2640, answer(10));
    assert_eq!(25164150, answer(100));    
}

#[cfg(test)]
//(1+...+100)^2 - (1^2 + ... +100^2)
// (100*101/2)^2 - ( ... )
fn answer(n: u64) -> u64{
    //1. a = (1+...+100)^2
    let mut a: u64 = get_seq_sum(n);
    a = a.pow(2);

    //2. b = (1^2 + ... +100^2)
    let b: u64 = get_square_sum(n);

    //3. a-b
    a - b    
}

#[cfg(test)]
fn get_seq_sum(n: u64) -> u64{
    n * (n+1) / 2
}

#[cfg(test)]
fn get_square_sum(n: u64) -> u64{
    let mut sum: u64 = 0;

    for i in 1..=n {
        sum += i.pow(2);
    }
    return sum;
}

//-----------------
// use (1^2 + ... +n^2) = n(n+1)(2n+1)/6

#[test]
fn test1(){
    assert_eq!(0, answer1(1));
    assert_eq!(4, answer1(2));
    assert_eq!(22, answer1(3));
    assert_eq!(2640, answer1(10));
    assert_eq!(25164150, answer1(100));    
}


//(1+...+100)^2 - (1^2 + ... +100^2)
// (100*101/2)^2 - ( ... )
#[cfg(test)]
fn answer1(n: u64) -> u64{
    //1. a = (1+...+100)^2
    let mut a: u64 = get_seq_sum(n);
    a = a.pow(2);

    //2. b = (1^2 + ... +100^2)
    let b: u64 = get_square_sum1(n);

    //3. a-b
    a - b    
}

//공식유도는 euler #6 설명 pdf 참조
#[cfg(test)]
fn get_square_sum1(n: u64) -> u64{
    n*(n+1)*(2*n+1)/6
}

 

끝