258. Add Digits

Description

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

Intuition

The problem can be solved using a straightforward mathematical approach based on the properties of numbers rather than iterative digit summation. The key observation is that the result of repeatedly summing the digits of a number until a single digit is obtained follows a pattern known as the "digital root." This can be computed using modular arithmetic.

Approach

1. Digital Root Concept: - The digital root of a number can be directly computed without iteration using the formula 1 + (num - 1) % 9. This formula gives the correct result for all numbers except 0, which requires special handling. - If num is 0, return 0 directly.
2. Implementation: - Implement the formula in a simple conditional structure to account for the special case where num = 0.
3. Edge Cases: - The only edge case is when num is 0, where the formula would incorrectly return 9 without a special case check.

Complexity

Time Complexity:

O(1). The calculation is done in constant time using a simple mathematical operation.

Space Complexity:

O(1). No extra space is used beyond the input variable.

Code

C++

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

Python

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

Java

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

JavaScript

/**
 * @param {number} num
 * @return {number}
 */
var addDigits = function(num) {
    
    return 1 + (num - 1) % 9;
};