We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Add Digits

Number: 258

Difficulty: Easy

Paid? No

Companies: Google, Meta, Amazon, Uber, Bloomberg, Microsoft, American Express, Adobe

Problem Description

Given a non-negative integer num, repeatedly sum its digits until the result is a single digit. Return that single-digit number.

Key Insights

  • The problem can be solved by repeatedly adding digits until a single digit is obtained.
  • A mathematical trick exists (digital root) that allows solving the problem in O(1) time without any loops or recursion.
  • The digital root of a non-zero number is 9 if the number is divisible by 9, otherwise it is num modulo 9.
  • Special handling is needed for the edge case where num is 0.

Space and Time Complexity

Time Complexity: O(1) Space Complexity: O(1)

Solution

The solution uses the mathematical property known as the digital root. Instead of repeatedly summing the digits using loops or recursion, the digital root can be calculated using a simple formula:

  1. If num is 0, the answer is 0.
  2. Otherwise, if num % 9 is 0, return 9.
  3. Else, return num % 9. This approach works because the digital root formula directly gives the result of repeatedly summing the digits until a single digit is obtained.

Code Solutions

# Function to add digits using the digital root formula.
def add_digits(num):
    # If the number is 0, directly return 0.
    if num == 0:
        return 0
    # If num is divisible by 9, then its digital root is 9.
    if num % 9 == 0:
        return 9
    # Otherwise, the digital root is num modulo 9.
    return num % 9

# Example usage:
print(add_digits(38))  # Expected output: 2
← Back to All Questions