CodeWars: sum of digits / digital root（02/21更新）

這也是這幾天遇到程式的面試題目，一併將解法分享٩(^ᴗ^)۶
題目：Codewars
一樣會用Ruby、Python和JavaScript三個語言來解題，讓我們開始吧！

今天解的是6kyu的難度，做這個題目前想到生命靈數也是這樣取的，把自己的西元出生年月日依序加起來，得到的個位數就是自己的生命靈數。

可以使用兩種方法來解，一種是遞迴，一種經由公式推導計算式，解法如下：

Ruby

1
2
3
4

#解法一
def digital_root(n)
  n < 10 ? n : digital_root(n.digits.sum)
end

遞迴(recursion)簡單來說就是函式會一直重複呼叫本身直到達成條件，
假如定義一個輸入值為digital_root(666)
第一次的結果為6 + 6 + 6 = 18，但值還沒有達到條件的n < 10，
所以會再重複呼叫一次，此時n = 18，1 + 8 = 9，
已經達到n < 10的條件，因此會回傳9

1
2
3
4

#解法二
def digital_root(n)
  n.zero? ? 0 : (n - 1) % 9 + 1
end

解法二就是之前常說的：如果在看到題目前多想一點，可以讓程式效率更高。
因為此字根是使用10進位制，每個字根都是過9進位，數字和 > 9時就要再重複相加，因此這裡的% 9就是簡化重複相加的步驟，以下舉例：

1
2
3

10 % 9 = 1
100 % 9 = 1
1000 % 9 = 1

這樣看來應該% 9就可以得到答案，為什麼答案會是n.zero? ? 0 : (n - 1) % 9 + 1呢？

第一個是因為如果輸入值剛好是0的話，應該直接返回0，因此在前面加了判斷式。

第二個是因為% 9遇到9的倍數就會出錯，為了避免這個情況，會需要先將n-1，%9後再+1，這樣遇到9的倍數答案也能正確～

2024/02/21更新

這幾天去面試收到的反饋，既然已經知道會有遇到9的倍數就出錯的問題，怎麼不直接寫在程式碼裡呢？因此就出現了解法三，看起來更清楚！

1
2
3
4
5
6
7
8
9
10
11

#解法三
def digital_root(n)
  case
  when n.zero?
    0
  when n % 9 == 0
    9
  else
    n % 9
  end
end

其實本題目也和鼎鼎大名的費氏列數解法相關，也有用到遞迴的概念，解法也一併補充在這裡：

1
2
3

def fibonacci(n)
  n <= 1 ? n : fibonacci(n - 1) + fibonacci(n - 2)
end

後面Python的解法和JS解法大致相同，只有寫法不同而已：

Python

1
2

def digital_root(n):
    return n if n < 10 else digital_root(sum(int(digit) for digit in str(n)))

1
2

def digital_root(n):
    return n if n == 0 else (n - 1) % 9 + 1

1
2
3
4
5
6
7

def digital_root(n):
    if n == 0:
        return 0
    elif n % 9 == 0:
        return 9
    else:
        return n % 9

JavaScript

1
2
3

function digitalRoot(n) {
    return n < 10 ? n : digitalRoot([...n.toString()].reduce((sum, digit) => sum + parseInt(digit), 0));
  }

1
2
3

function digitalRoot2(n) {
    return n === 0 ? 0 : (n - 1) % 9 + 1;
}

1
2
3
4
5
6
7
8
9
10

function digitalRoot(n) {
  switch (true) {
    case n === 0:
      return 0;
    case n % 9 === 0:
      return 9;
    default:
      return n % 9;
  }
}