016. Power Digit Sum ($2^{1000}$과 같은 큰 지수승 구하기)

​문제 (English)

$2^{15} = 32768$ and the sum of its digits is $3+2+7+6+8=26$.

What is the sum of the digits of the number of $2^{1000}$?

 

Answer: 1366

문제 분석

---

$2^{1000}$을 십진수로 나타내면 자릿수가 302자리로 일반적인 변수 u64, u128로는 계산이 안된다.

$ 1 + 1000 \times Log_{10}{2} = 302 $

 

각 자리를 배열로 나타내고, 그 배열값에 대해 2를 곱하는 형태로 하면, 302 자릿수에 대해서도 계산이 되겠다.

 

풀이 1 

---

$2^{15}$에 대해 생각해보자. 자릿수는 $1+15\times log{2}=5$

 

5자리의 배열을 만들고, arr[0]=1에서 출발해서 2를 곱해 나가자.

만약 곱한 값이 10 미만이면 그대로 곱한 값을 쓰고, 10 이상이면 carry 1을 넘겨주는 형태로.

 

fn answer(n:usize) -> usize {
    //1. calculate ditits. if n=15, 2^15=32768. digits = 1 + 15*Log2 = 5
    let digits = 1 + (n as f32 * std::f32::consts::LOG10_2) as usize;

    //2. make arry with digits length
    let mut narr:Vec<usize> = vec![0; digits];       
    narr[0] = 1;

    //3. loop with multiply 2
    let mut order:usize = 0;
    for _ in 0..n {
        let mut carry:usize = 0;                
        let mut j:usize = 0;
        while j <= order {
            let p = narr[j] * 2 + carry;
            narr[j] = p % 10;                        
            carry = p / 10;

            //if carry exist then encrese order
            if j == order && carry > 0 { 
                order += 1;                 
            }
            j += 1;
        }
    }    
    return narr.into_iter().sum();  
}

이 코드로 hackerrank도 통과할 수 있다.

총평

---

아주 큰 수에 대한 곱셈을, 배열로 만들어서 처리할 수 있느냐를 물어보는 문제. 

큰 수와 큰 수간의 곱셈을 처리하는 것은 꽤 복잡하나, 큰 수에 2를 곱하는 것은 비교적 쉽게 구현이 가능하다.

 

전체 소스코드

---

p16.rs 

//알고리즘 구상
//- 2^1000은 1+1000Log(2)=302자리 수. 따라서, u128로도 처리할 수 없음
//- 302자리 수에 대해, 처음 1부터 시작해서 2씩 곱해나가면, 4,8,16...이 되고, 1000번 곱하면 2^1000이 된다.
//- 즉, 배열처럼 된 십진수 값에 대한 곱셈 연산을 짜게하는 문제
//  1: 0001 * 2 = 0002
//  2: 0002 * 2 = 0004
//  3: 0004 * 2 = 0008
//  4: 0008 * 2 = 0016
//  5: 0016 * 2 = 0032
//  6: 0032 * 2 = 0064

#[test]
fn test(){
    assert_eq!(26, answer(15)); //2^15=32768, 3+2+7+6+8=26
    assert_eq!(1366, answer(1000));
}

#[cfg(test)]
fn answer(n:usize) -> usize {
    //1. calculate ditits. if n=15, 2^15=32768. digits = 1 + 15*Log2 = 5
    let digits = 1 + (n as f32 * std::f32::consts::LOG10_2) as usize;

    //2. make arry with digits length
    let mut narr:Vec<usize> = vec![0; digits];       
    narr[0] = 1;

    //3. loop with multiply 2
    let mut order:usize = 0;
    for _ in 0..n {
        let mut carry:usize = 0;                
        let mut j:usize = 0;
        while j <= order {
            let p = narr[j] * 2 + carry;
            narr[j] = p % 10;                        
            carry = p / 10;

            //if carry exist then encrese order
            if j == order && carry > 0 { 
                order += 1;                 
            }
            j += 1;
        }
    }    
    return narr.into_iter().sum();  
}

 

끝