Add Digits

Problem

Given an integer num, repeatedly add all its digits until the result has only one digit, and return it.

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

Constraints

• 0 <= num <= 231 - 1

Solution

The problem Add Digits can be solved by calculating modulo 9 of the given number. This can be proven in the following way. Let F(num) = x where F(num) is the outcome of an integer num. If x < 9 then F(num + 1) = x + 1. If x = 9 then F(num + 1) = F(x + 1) = F(10) = 1. Since F(1) == 1, F effectively calculates modulo 9 of the given number except for the case when the outcome is 0 when the input is not 0, in which case it returns 9 instead.

Implementation

class Solution
{
  public:
    int addDigits(int num)
    {
        if (num == 0)
            return 0;

        return num % 9 == 0 ? 9 : num % 9;
    }
};