C++ Coding Exercise – Add Digit – Digit Root

Given a non-negative integer number, 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.

Submit your solution at: https://leetcode.com/problems/add-digits/

Naive Solution – Simulation

We simulate how it works by adding all digits until the sum is less than 10.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int addDigits(int num) {
        while (num > 0) {
            int cnt = 0;
            while (num > 0) {
                cnt += num % 10;  // sum up each digit
                num /= 10;
            }
            if (cnt < 10) return cnt;
            num = cnt;  // make sum the new number
        }
        return 0;
    }
};

class Solution {
public:
    int addDigits(int num) {
        while (num > 0) {
            int cnt = 0;
            while (num > 0) {
                cnt += num % 10;  // sum up each digit
                num /= 10;
            }
            if (cnt < 10) return cnt;
            num = cnt;  // make sum the new number
        }
        return 0;
    }
};

1101 / 1101 test cases passed. Runtime: 12 ms

O(1) Math Solution

Based on the Wiki Page – Digit Root, we know that (1), the multiples of 9 has a digit root = 9, for example, 9, 18 (1+8), 27 (2+9), 189 (1+8+9=18=1+8) etc. and any other non-negative integers have a digit root which is 1 + floor((n – 1) % 9). For example, 11 is the second number after 9, so it has a digit root equals to 1 + ((11 – 1) % 9) = 2.

82 is the first number after multiples of 9, so the digit root = 1 + ((82 – 1) % 9) = 1.

1
2
3
4
5
6

class Solution {
public:
    int addDigits(int num) {
        return 1 + ((num - 1) % 9);
    }
};

class Solution {
public:
    int addDigits(int num) {
        return 1 + ((num - 1) % 9);
    }
};

Runtime: 8ms.

–EOF (The Ultimate Computing & Technology Blog) —