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

Example:

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

#### Approach 1: Linear approach

```int addDigit(int num) {
int digitalRoot = 0;
while(num) {
digitalRoot += num % 10;
num /= 10;
if(num == 0 && digitalRoot > 9) {
num = digitalRoot;
digitalRoot = 0;
}
}
return digitalRoot;
}

```

#### Complexity Analysis

• Time complexity : O(n).
• Space complexity : O(1).

Recursive solution

```int addDigit(int num) {
if(num < 10) return num;
int digitalRoot = 0;
while(num) {
digitalRoot += (num % 10);
num /= 10;
}
}

```

#### Approach 2: Mathematical - Digital Root

Digital root is a school math concept.

The digital root is the difference between the number and the largest multiple of 9 less than the number itself.

```Digital Root of 1000 is 1.
Largest multiple of 9 is less then 1000 = 9 * 11 = 999
So digital root = 1000 - 999 = 1;

Digital Root of 38 is 2;
Largest multiple of 9 is less then 38 = 9 * 4 = 36
So digital root = 38 - 36 = 2;

```

Actually if we divide any number with 9 then reminder will be the digital root.

```Digital Root of 1000 is 1. by 1000 % 9 = 1
Digital Root of 38 is 2. by 38 % 9 = 2

```

But what if the number is itself multiple of 9 what will happened then? Simple 9 will be the digital root of that number then.

```int addDigit(int num) {
if(num == 0) return 0;
if(num % 9 == 0) return 9;
return num % 9;
}

```

We can reduce it to one line solution 😙

```int addDigit(int num) {
return 1 + (num - 1) % 9;
}

```

#### Complexity Analysis

• Time complexity : O(1).
• Space complexity : O(1).