You are given a non-negative integer num.
Your task is to repeatedly add all its digits until only one digit remains.

This final single digit is also known as the digital root.

---

Understanding the Problem

You repeatedly sum the digits of the number:

Example:
num = 38
3 + 8 = 11
1 + 1 = 2
So the answer is 2.

Example:
num = 0 → output = 0
num = 99 → 9 + 9 = 18 → 1 + 8 = 9

The main idea is to continue digit addition until the number becomes a single digit.

---

Approach (Explained in Simple Language)

There are two main ways to solve this problem.

1. Repeatedly sum digits using loops

This approach adds digits until the value becomes a single digit.

Steps:
Take the number
Sum all its digits
If the sum is greater than 9, repeat
Else return the sum

This is straightforward but may require multiple iterations.

2. Use the digital root formula

A mathematical shortcut gives the answer in constant time.

digital root =
0 if num = 0
1 + (num − 1) % 9 otherwise

This formula works because of the way numbers behave in modulo 9 arithmetic.

This is the optimal O(1) solution.

---

Java Code (Loop-Based Approach)

public class AddDigits {

    public int addDigits(int num) {

        while (num >= 10) {

            int sum = 0;
            int temp = num;

            while (temp > 0) {
                sum += temp % 10;
                temp /= 10;
            }

            num = sum;
        }

        return num;
    }

    public static void main(String[] args) {
        AddDigits solution = new AddDigits();
        System.out.println(solution.addDigits(38));
    }
}

---

Java Code (Digital Root Formula – Optimal)

public class AddDigitsFormula {

    public int addDigits(int num) {

        if (num == 0) {
            return 0;
        }

        return 1 + (num - 1) % 9;
    }

    public static void main(String[] args) {
        AddDigitsFormula solution = new AddDigitsFormula();
        System.out.println(solution.addDigits(38));
    }
}

---

Dry Run (Loop-Based Summation)

Let num = 38

num = 38
num >= 10 → continue

Inner loop:
temp = 38
sum = 0

sum = 8
temp = 3
sum = 8 + 3 = 11
temp = 0

num = 11

---

num = 11
num >= 10 → continue

Inner loop:
temp = 11
sum = 0

sum = 1
temp = 1

sum = 1 + 1 = 2
temp = 0

num = 2

Now num < 10 → stop.

Output = 2

---

Dry Run (Digital Root Formula)

num = 38

digital root = 1 + (num − 1) % 9
= 1 + (37 % 9)
= 1 + 1
= 2

Result = 2

---

Why This Approach Works

The repeated-digit-sum method is intuitive and follows the problem definition directly.

However, the digital root formula uses mathematical properties to compute the final value instantly:

All integers eventually reduce to their modulo 9 equivalence
Except that modulo 9 gives 0 for multiples of 9, while digital root gives 9
Hence the formula adjusts using 1 + (num − 1) % 9

This gives O(1) time complexity.