PU Add Digits

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

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?

C Solution 1:

int addDigits(int num) {
    if (num < 10) return num;
    int res = 0;
    while (num) {
        res += num % 10;
        num /= 10;
    }
    return addDigits(res);
}

C Solution 2:

int addDigits(int num) {
    while (num > 9) {
        num = num % 10 + num / 10;
    }
    return num;
}

C Solution 3:

int addDigits(int num) {
    if (num < 10) return num;
    int res = num % 9;
    return res ? res : 9;
}

C Solution 4:

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

C Solution 5:

int addDigits(int num) {
    if (!num) return 0;
    num %= 9;
    return num ? num : 9;
}

Summary:

• The difference between a * 100 + b * 10 + c and a + b + c is a * 99 + b * 9 which is 9 * M (M is a non-negative integer), so just use num %= 9 to get rid of the largest 9 * M.
  • But there is a corner case where num is 0.
• Solution 4 is wiki's answer, but it's not obvious.
• For me, solution 5 is better, we can think of solution 4 as a improved version of solution 5 which covers the corner case.

LeetCode: 258. Add Digits