# Add Digits
**Difficulty:** EASY
[External](https://leetcode.com/problems/add-digits)
Canonical: https://scaleengineer.com/dsa/problems/add-digits
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
**Companies:** [American Express](https://scaleengineer.com/companies/american-express)
---
## Problem
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 <= 231 - 1`

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

# Approaches
## Iterative Approach
Use a while loop to repeatedly sum the digits of the number until we get a single digit.
**Time:** O(log n) - where n is the input number, as we need to process each digit · **Space:** O(1) - only using constant extra space
**Pros:** Easy to understand and implement; Works for all positive integers; Straightforward logic
**Cons:** Not the most efficient solution; Uses loops which might not be optimal; Time complexity depends on the number of digits
### Explanation
In this approach, we use a while loop that continues as long as the number has more than one digit (num > 9). In each iteration, we extract each digit using the modulo operator (%) and integer division (/), and add them together. This process continues until we get a single digit.

```java
public int addDigits(int num) {
    while (num > 9) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        num = sum;
    }
    return num;
}
```
### Algorithm
1. While number is greater than 9 (has more than one digit):
   - Initialize sum as 0
   - While number is greater than 0:
     * Add the last digit (num % 10) to sum
     * Remove the last digit (num /= 10)
   - Set number to sum
2. Return the final single digit

## Recursive Approach
Use recursion to sum the digits until we get a single digit number.
**Time:** O(log n) - where n is the input number, as we need to process each digit · **Space:** O(log n) - due to recursive call stack
**Pros:** Clean and elegant solution; Easy to understand the logic; Code is more concise
**Cons:** Uses recursion which consumes stack space; Not as space efficient as iterative solution; Still not the most optimal solution
### Explanation
This approach uses recursion to solve the problem. We first calculate the sum of digits, and if the sum is greater than 9, we recursively call the function with the sum as the new input.

```java
public int addDigits(int num) {
    if (num < 10) return num;
    
    int sum = 0;
    while (num > 0) {
        sum += num % 10;
        num /= 10;
    }
    return addDigits(sum);
}
```
### Algorithm
1. If number is less than 10, return the number
2. Calculate sum of digits:
   - While number is greater than 0:
     * Add the last digit to sum
     * Remove the last digit
3. Recursively call function with sum

## 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.
**Time:** O(1) - constant time operation regardless of input size · **Space:** O(1) - only using constant extra space
**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
### Explanation
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.

```java
public int addDigits(int num) {
    if (num == 0) return 0;
    if (num % 9 == 0) return 9;
    return num % 9;
}
```
### Algorithm
1. If number is 0, return 0
2. If number is divisible by 9, return 9
3. Otherwise, return number mod 9

# Solutions
### Java

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

```

### CPP

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

```

### Python

```python
class Solution:
    def addDigits(
        self, num: int) -> int: return 0 if num == 0 else (num - 1) % 9 + 1

```