Add Digits

EASY

Description

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

Example 1:

Input: num = 38
Output: 2
Explanation: The process is
38 --> 3 + 8 --> 11
11 --> 1 + 1 --> 2 
Since 2 has only one digit, return it.

Example 2:

Input: num = 0
Output: 0

Constraints:

0 <= num <= 2³¹ - 1

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

Approaches

Checkout 3 different approaches to solve Add Digits. Click on different approaches to view the approach and algorithm in detail.

Mathematical Approach (Digital Root)

Use the concept of digital root in mathematics to solve the problem in O(1) time without any loops or recursion.

Algorithm

If number is 0, return 0
If number is divisible by 9, return 9
Otherwise, return number mod 9

This approach uses the mathematical concept of digital root. For a non-zero number num, its digital root is congruent to num mod 9. If num is divisible by 9, the digital root is 9, else it's num mod 9. For zero, the digital root is 0.

public int addDigits(int num) {
    if (num == 0) return 0;
    if (num % 9 == 0) return 9;
    return num % 9;
}

Complexity Analysis

Time Complexity: O(1) - constant time operation regardless of input sizeSpace Complexity: O(1) - only using constant extra space

Pros and Cons

Pros:

O(1) time complexity
No loops or recursion needed
Most efficient solution
Constant space complexity

Cons:

Requires understanding of digital root concept
Might be less intuitive at first glance
Could be harder to explain in an interview setting

Code Solutions

Checking out 3 solutions in different languages for Add Digits. Click on different languages to view the code.

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

Video Solution

Watch the video walkthrough for Add Digits

Patterns:

MathNumber Theory

Companies:

American Express |