Digit Root

Digit root

 

어떤 숫자 num에 대해 아래 과정을 취했을 때 나올 수 있는 값을 구해보자.

1. 각 자리의 숫자들을 다 더한다.
2. 만약 다 더한값이 한자리 수라면 이 수를 반환한다.
3. 두자리 수 이상이라면 그 수에 대해 다시 1부터 수행한다.

예를 들어 12345 의 경우 아래의 과정을 거쳐 6이된다.

1. 1 + 2 + 3 + 4 + 5 = 15
2. 1 + 5 = 6

이떄 6은 15의 10진수 digit root이다.

다음과 같이 작성하기도 한다.

$$
dr_{10}(15) = 6
$$

위 값을 구하는 Leetcode 문제도 존재한다.
(https://leetcode.com/problems/add-digits/description/)

Digit root 를 구하기 위해 코드를 작성할 때 반복문 혹은 재귀를 사용하는 방법이 먼저 생각날 것이다.

아래의 코드는 반복문으로 각 자리수의 숫자를 더하고, 10 미만인 경우 바로 결과를 반환, 10 이상인 경우 재귀를 통하여 답을 구하도록 작성되어있다.

int dr(int num) {
    int total = 0;
    while(num > 0){
        total += (num % 10);
        num /= 10;
    }
    return total < 10 ?  total : dr(total);
}

하지만 수학을 좀 사용하면 시간 복잡도 O(1)에 구할 수 있다.

int dr(n){
    if(n==0) return 0;
    if(n%9 != 0) return n % 9;
    return 9
}

위의 식이 왜 작동하는지는 아래의 수식을 보면 알 수 있다.

$$
\begin{align*}dr_b(n) &\equiv d_ib^i + ... + d_2b^2 + d_1b^1 + d_0b^0 \\ &\equiv d_i (1) + ... + d_2 (1) + d_1 (1) + d_0 (1) \\ &\equiv d_i + ... + d_2 + d_1 + d_0 \pmod{(b-1)} \end{align*}
$$

위 식은 어느 b진법 수를 (b-1)로 나누었을 때의 나머지와 같은 수의 b진법 상에서의 각 자리에서의 수를 더한 값을 (b-1)로 나누었을때의 나머지가 같다는 것을 보여준다.

위 수식이 왜 작동하는지 알기위해서는 모듈러 연산의 성질중 아래 내용을 알아야한다.

 

만약 $a_1 \equiv b_1 \pmod{m}$ 이면서 $a_2 \equiv b_2 \pmod{m}$ 일때 아래 내용이 성립한다.

1. 0 이상의 정수 k에 대해 $a_1^k \equiv b_1^k \pmod{m}$
2. $a_1 + a_2 \equiv b_1 + b_2 \pmod{m}$
3. 정수 k에 대해 $ka_1 \equiv kb_1 \pmod{m}$

이 내용을 기반으로 위의 식 결과가 나오는 이유를 알 수 있다.

• 우선 $b \equiv 1 \pmod{(b-1)}$ 이다.
• 3번 성질에 의해 $d_ib^i \equiv d_i(1) \pmod{(b-1)}$ 이다.
• 2번 성질을 이용하면 $b^k \equiv 1^k \equiv 1 \pmod{(b-1)}$ 임을 알 수 있다.
• 1번 성질에 의해 $d_ib^i + ... + d_1b^1 + d_0b^0 \equiv d_i (1) + ... + d_1 (1) + d_0 (1) \pmod{(b-1)}$ 이다.

만약 $d_i + ... + d_1 + d_0$이 한자리수가 아니라고 해도 이를 다시 $d'_jb^j + ... + d'_1b^1 + d'_0b^0$ 으로 잡고 계산을 수행하면 $dr_b(n) \equiv d'_j + ... + d'_1 + d'_0 \pmod{(b-1)}$ 이란 결과를 얻을 것이다.

 

$0 \le dr_b(n) \le (b-1)$ 인데, (b-1)의 배수가 아닌 경우 $0 \lt dr_b(n) \lt (b-1)$ 이다. 이때 $dr_b(n) \mod{(b-1)} = dr_b(n)$ 임으로 $dr_b(n) = n \mod{(b-1)}$ 이게 된다.

 

$dr_b(n) \mod{(b-1)} = 0$ 인 경우를 고려해보자. $dr_b(n)$이 0이거나 b-1의 배수일 때이다. $dr_b(n)$이 0인 경우는 n이 0인 경우일때 밖에 없다. 따라서 $dr_b(n) \mod{(b-1)} = 0$ 이면서 $n \ne 0$ 인 경우는 $dr_b(n)$이 0이 아닌 b-1의 배수일 때인데 $0 \le dr_b(n) \le (b-1)$ 임으로 이때는 $dr_b(n) = b-1$ 이다.

 

위 내용을 종합하면 아래의 식과 같다.

$$
dr_b(n) = \begin{cases} 0 & \text{if } n = 0 \\ n \mod (b-1) & \text{else if } n \ne 0 \land n \not\equiv 0 \pmod{(b-1)} \\ b-1 & \text{else}\end{cases}
$$

 

초반에 언급하였던 시간복잡도 O(1)의 코드 내용과 같다.

 

10진수에 대한 digit root를 구할 때는 다음과 같이 한줄로도 작성할 수 있다.

int dr10(int n) {
    return 1 + (n - 1) % 9;
}