258. Add Digits

EasyMathNumber TheorySimulation
Leetcode Link

Problem Description

Given an integer num, the task is to reduce this number to a single digit by adding its constituent digits together. If the sum is still not a single digit, the process should be repeated with the new sum until only one digit remains. For example, if the input is num = 38, the process would be:

  • 3 + 8 = 11
  • 1 + 1 = 2 Since 2 is a single digit, 2 is the final result. This process is often referred to as digital root or repeated digital sum.

Intuition

The solution to this problem uses a number theory concept known as digital root. The digital root of a non-negative integer is the position it holds relative to the largest multiple of 9 less than or equal to the number. It can be observed that the digital root of any number is a pattern that repeats every 9 numbers and is related to the modulo operation.

For any number n > 9, the digital root is equivalent to 1 + ((n - 1) % 9). This is because numbers 1 through 9 have a digital root which is the number itself, and the pattern then repeats from 10 onwards, with 10 having a digital root of 1 again, 11 having a digital root of 2, and so on.

Therefore, the solution directly calculates this value without the need to iteratively add the digits of the number. It handles the edge case of 0 separately, as its digital root should be 0. The given code uses this principle to return the digital root in a single line:

  • If num is 0, return 0.
  • If num is not 0, apply the digital root formula: (num - 1) % 9 + 1.

Learn more about Math patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Solution Approach

The implementation of the solution utilizes a mathematical shortcut to find the digital root of an integer, eliminating the need for iteration or recursion. This solution does not use any complex data structures or algorithms but simply applies a mathematical formula to accomplish the task in constant time complexity O(1). Below is an explanation of the code provided in the reference solution:

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

The algorithm follows these steps:

  1. Check if num is 0. If it is, the digital root is also 0. This case is handled separately because the modulo operation does not apply to 0 as we want the digital root of 0 to be 0.
  2. If num is not 0, apply the digital root formula (num - 1) % 9 + 1.

The method is based on the property that for any number n the sum of its digits until a single digit is achieved (its digital root) is equal to that number modulo 9, except for multiples of 9 where the result is 9 and not 0. The formula (num - 1) % 9 + 1 effectively transforms the range of num % 9, which is 0 to 8, to 1 to 9, catering to the digital root definition.

This concise approach makes the implementation very efficient since it does not involve any loops, recursion, or the use of additional data structures, hence the constant time complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which type of traversal does breadth first search do?

Example Walkthrough

To demonstrate the solution approach, let's take num = 94 as our example.

  • Normally, we would add the digits 9 + 4 = 13.
  • Next, we would add 1 + 3 to get 4.

Using our one-liner formula, we can arrive at the same result without doing the two-step summation process:

  1. We first check if the number is 0, which it is not.
  2. We apply the formula (num - 1) % 9 + 1:
    • (94 - 1) % 9 + 1
    • 93 % 9 + 1
    • As 93 is a multiple of 9, 93 % 9 is 0.
    • Finally, 0 + 1 is 1.

The result is 1 for our input 94, but we need a single digit other than 0 (since we took 94, not a multiple of 9), we add 1 to our 0 result to correct the range, thus our single digit is 1.

This simple example illustrates the efficiency of using the digital root formula, bypassing the need for multiple summing steps.

Solution Implementation

1class Solution:
2    def add_digits(self, num: int) -> int:
3        """
4        This method uses the digital root concept, which in
5        this case can be computed using the modulo operation.
6        The digital root is a single-digit value obtained by
7        an iterative process of summing digits, on each iteration
8        using the result from the previous iteration to compute the sum
9        of digits until a single-digit number is obtained.
10
11        :param num: The number from which we need to find the digital root.
12        :return: The digital root of the given number.
13        """
14        # If the number is 0, the digital root is also 0.
15        if num == 0:
16            return 0
17        # For all other numbers, compute the digital root using the formula:
18        # (num - 1) % 9 + 1. This works because it maps a number to its
19        # digital root, which is the remainder when divided by 9,
20        # except when the number is a multiple of 9, then the result
21        # is 9 instead of 0, hence the '-1' before modulo and '+1' after.
22        else:
23            return (num - 1) % 9 + 1
24
25# Example usage:
26# sol = Solution()
27# print(sol.add_digits(38))  # Output would be 2
28
1class Solution {
2    // Method to add the digits of an integer until the sum is a single digit
3    public int addDigits(int num) {
4        // This algorithm is based on the digital root concept, which can be computed
5        // using the formula below. The result is the same as summing the digits
6        // until a single digit is reached.
7        // The expression '(num - 1) % 9' gives a result in the range 0-8 for all
8        // positive integers, which is then offset by adding 1 to get a range from 1-9.
9        // It handles the case when num is a multiple of 9 correctly, which should return 9.
10        return (num - 1) % 9 + 1;
11    }
12}
13
1class Solution {
2public:
3    // Function to add the digits of a number until the result is a single digit.
4    int addDigits(int num) {
5        // Using Digital Root formula which is a well-known and proven method for this problem.
6        // If the number is 0, the digital root is 0.
7        if (num == 0) { 
8            return 0; 
9        }
10        // For all other numbers, the digital root is the remainder when the number
11        // is divided by 9, with a special case when num is a multiple of 9.
12        else {
13            // Subtract 1 from num to handle the multiple of 9 scenario, then
14            // mod by 9 to get the remainder, and add 1 to adjust for the initial subtraction.
15            return (num - 1) % 9 + 1;
16        }
17    }
18};
19
1// Function to add the digits of a number until the result is a single digit.
2function addDigits(num: number): number {
3    // If the number is 0, the digital root is 0.
4    if (num === 0) {
5        return 0;
6    }
7    // For other numbers, use the Digital Root formula, which is a subtraction of 1, 
8    // modulus operator (to find the remainder when diving by 9), and then an addition of 1.
9    // This handles the case where num is a multiple of 9, and provides the correct digital root.
10    else {
11        // Subtract 1 from num before applying modulus operator
12        // Then add 1 after modulus operation to obtain the correct digital root
13        return ((num - 1) % 9) + 1;
14    }
15}
16
Not Sure What to Study? Take the 2-min Quiz：

Which of the following shows the order of node visit in a Breadth-first Search?

Time and Space Complexity

The time complexity of the given code is O(1). This is because the calculation num - 1) % 9 + 1 is a constant-time operation, unrelated to the size of the input num. The function performs a single arithmetic operation regardless of the value of num, so the time it takes to run does not change with larger inputs.

The space complexity of the code is also O(1). The algorithm uses a fixed amount of space for the computations; it does not allocate any additional space that grows with the input size. There are no data structures used that would scale with the size of num, only a few variables for the calculation.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫