首页 > itarticle > l258 add digits

l258 add digits

admin 11月 13, 2020 0

题目描述

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

解题思路

使用递归的方式，计算各个位数和s是否小于10，如果小于10返回，否则递归求s的各位数和

数根：使用数学公式 https://en.wikipedia.org/wiki/Digital_root#Congruence_formula

L258

Go递归

func addDigits(num int) int {
    s:=0

    for num>0 {
        s += num%10
        num /= 10
    }

    if s<10 {
        return s
    }else{
        return addDigits(s)
    }
}

Go实现O(1)算法

1
2
3

func addDigits(num int) int {
    return 1 + (num - 1) % 9
}