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

Example:

Input: 29
Output: 2 
Explanation: 2 + 9 = 11, 1 + 1 = 2. 
             Since 2 has only one digit, return it.

Approach: Algorithm is simple:

• IF num eq 0, return 0
• ELSE IF num % 9 eq 0, return 9
• ELSE return num % 9

Why num % 9 works. Let's see:

Let’s say that your positive number is N. Writing N in terms of its digits is

N = (sum) [ d[j] * 10^j ], where d[0], d[1], d[2], …. are the digits of N. The sum starts at j=0.

Notice now that 10^1 = (9*1 + 1), 10^2 = (9*11 + 1), 10^3 = (9*111 + 1), and so on. Rearrange to write

N = (9*1 + 1) d[0] + (9*11 + 1) d[1] + (9*111 + 1) d[2] + …

= 9 * (1 d[0] + 11 d[1] + 111 d[2] + ….. ) + d[0] + d[1] + d[2] + ….

= multiple of 9 + d[0] + d[1] + d[2] + ….

Thus N (mod 9) = d[0] + d[1] + d[2] + ….

Implementation in C#: 

        public int AddDigits(int num) 

       {

            if (num == 0)

            {

                return 0;

            }

        

            int sum = num % 9;

            return sum == 0 ? 9 : sum;

        }

Complexity: O(1)