Domain 1EasyCORE

Add Digits

The problem requires us to repeatedly sum the digits of an integer until we obtain a single-digit result. The input is a non-negative integer `num` within the range `[0, 2^31 - 1]`. The output should be a single-digit integer. An edge case to consider is when `num` is 0, which should directly return 0 without any processing.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Math

258. Add Digits

Model: qwen2.5-coder:14b
Topics: Math
FAANG asked: 1
Acceptance rate: 58.7%


Problem Breakdown

The problem requires us to repeatedly sum the digits of an integer until we obtain a single-digit result. The input is a non-negative integer num within the range [0, 2^31 - 1]. The output should be a single-digit integer. An edge case to consider is when num is 0, which should directly return 0 without any processing.

Intuition

A brute-force approach would involve repeatedly summing the digits of the number until we get a single digit. This can be done using loops or recursion. However, this approach has a time complexity of O(log n) per iteration due to the need to extract and sum digits, and it may require multiple iterations for larger numbers.

The key insight is to recognize that there is a mathematical pattern in the results. For any non-negative integer num, the result of repeatedly adding its digits until a single digit is obtained can be found using the digital root formula: 1 + (num - 1) % 9. This works because of properties related to modular arithmetic and number theory, particularly in base 10.

Approach

We will use the digital root formula to directly compute the result in constant time without any loops or recursion. The approach involves:

  1. If num is 0, return 0.
  2. Otherwise, return 1 + (num - 1) % 9. This handles the case where num is a multiple of 9 correctly by returning 9.

Complexity Analysis

  • Time complexity: O(1) - The solution involves a constant number of operations regardless of the input size.
  • Space complexity: O(1) - No additional space is used beyond a few variables.

Solution

def addDigits(num):
    if num == 0:
        return 0
    else:
        return 1 + (num - 1) % 9

Edge Cases Handled

  • Edge Case: num = 0 - The function directly returns 0, as the digital root of 0 is 0.
  • Edge Case: Multiples of 9 - For numbers like 18, 27, etc., the function correctly returns 9, as these are multiples of 9 and their digital roots are always 9.