LeetCode 258: Add Digits Solution in Python – A Step-by-Step Guide

What Is LeetCode 258: Add Digits?

In LeetCode 258: Add Digits, you’re given a non-negative integer num, and your task is to return the single digit you get by repeatedly adding all its digits until only one remains. This process is called finding the "digital root." It’s a fun math problem with a coding twist, related to challenges like LeetCode 202: Happy Number, but simpler and focused on digit summing.

Problem Statement

• Input: A non-negative integer num.
• Output: An integer—the single-digit result after summing digits repeatedly.
• Rules: Keep adding all digits until you have one digit; use 0 for input 0.

Constraints

• num: 0 to 10^9.

Examples

• Input: num = 38
• Output: 2 (38 → 3 + 8 = 11 → 1 + 1 = 2).
• Input: num = 0
• Output: 0 (already one digit).
• Input: num = 123
• Output: 6 (123 → 1 + 2 + 3 = 6).

Understanding the Problem: Summing to One Digit

To solve LeetCode 258: Add Digits in Python, we need to take a number, add up all its digits, and if the result has more than one digit, do it again until we’re left with just one. For example, with 38, we go 3 + 8 = 11, then 1 + 1 = 2. A straightforward way—adding digits over and over—works fine, but there’s a faster trick using math. We’ll use two methods: 1. Best Solution (Mathematical Congruence Formula): O(1) time—super quick and clever. 2. Alternative Solution (Iterative Digit Summing): O(log n) time—simple and clear.

Let’s dive into the best solution with a friendly, detailed walkthrough.

Best Solution: Mathematical Congruence Formula

Why This Is the Best Solution

The mathematical congruence formula approach is the top pick for LeetCode 258 because it solves the problem in O(1) time—meaning it takes the same tiny amount of time no matter how big the number is. It uses a cool math trick called the digital root formula, skipping all the repeated adding, which makes it both fast and exciting to learn.

How It Works

Think of this solution as a magic shortcut: instead of adding digits step-by-step, you use a special rule that tells you the final single digit right away. This rule comes from a math idea called "congruence modulo 9," but don’t worry—it’s easier than it sounds! Here’s how it works, step-by-step, explained in a way that’s simple to follow:

• Step 1: What’s the Pattern?:
• When you add digits repeatedly, numbers follow a cycle tied to 9.
• Examples:
• 9 → 9 (one digit).
• 10 → 1 + 0 = 1.
• 18 → 1 + 8 = 9.
• 19 → 1 + 9 = 10 → 1 + 0 = 1.
• Notice: Numbers divisible by 9 end at 9, others loop around.
• Step 2: The Magic Rule:
• There’s a formula: for any number n, its digital root is 1 + ((n - 1) % 9) if n > 0, or 0 if n = 0.
• What’s %? It’s the remainder when you divide by 9 (e.g., 10 % 9 = 1).
• Why this works:
• Numbers repeat every 9: 1, 2, 3, 4, 5, 6, 7, 8, 9, then back to 1.
• Subtract 1, take remainder, add 1—it maps any number to 1-9, or 0 for 0.
• Step 3: Apply the Formula:
• For 38:
• (38 - 1) % 9 = 37 % 9 = 1 (37 ÷ 9 = 4 remainder 1).
• 1 + 1 = 2.
• For 0: Special case, return 0.
• Step 4: Why It’s Cool:
• No loops, no summing—just one quick calculation!

It’s like having a secret code: plug in the number, and out pops the answer, no fuss!

Step-by-Step Example

Example: num = 38

• Step 1: Use the Formula:
• n = 38.
• Subtract 1: 38 - 1 = 37.
• Remainder when divided by 9: 37 % 9 = 1 (37 = 9 * 4 + 1).
• Add 1: 1 + 1 = 2.
• Step 2: Check:
• 38 → 3 + 8 = 11 → 1 + 1 = 2 (matches!).
• Result: 2.

Example: num = 123

• Step 1:
• 123 - 1 = 122.
• 122 % 9 = 5 (122 = 9 * 13 + 5).
• 1 + 5 = 6.
• Step 2:
• 123 → 1 + 2 + 3 = 6 (matches!).
• Result: 6.

Example: num = 0

• Step 1: n = 0, return 0 directly.
• Result: 0.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained in a friendly way:

Copy codeclass Solution:
    def addDigits(self, num: int) -> int:
        # Step 1: Handle the special case
        if num == 0:
            return 0  # Zero stays zero

        # Step 2: Use the magic formula
        # (num - 1) % 9 gives us 0-8, then +1 makes it 1-9
        return 1 + ((num - 1) % 9)

• Time Complexity: O(1)—just one calculation, no matter the size!
• Space Complexity: O(1)—no extra space needed.

This solution is like a math wizard’s spell—one line, and you’re done!

Alternative Solution: Iterative Digit Summing

Why an Alternative Approach?

The iterative digit summing method takes the long road, adding digits step-by-step until you reach one, like following a recipe to bake a cake. It’s slower but shows you exactly how the process works, making it a great way to understand the problem before jumping to the shortcut.

How It Works

Picture yourself with a calculator, breaking down the number into digits, adding them up, and repeating until you’ve got just one digit left. Here’s how it works, step-by-step:

• Step 1: Start with the Number:
• Take num (e.g., 38).
• Step 2: Add the Digits:
• Split 38 into 3 and 8, add them: 3 + 8 = 11.
• Step 3: Check and Repeat:
• 11 has two digits, so add again: 1 + 1 = 2.
• 2 is one digit—stop!
• Step 4: Use a Loop:
• Keep doing this in a loop until the number is 0-9.

It’s like peeling an onion—layer by layer until you reach the core!

Step-by-Step Example

Example: num = 38

• Step 1: Start with 38.
• Step 2: 3 + 8 = 11.
• Step 3: 11 → 1 + 1 = 2.
• Step 4: 2 is one digit.
• Result: 2.

Example: num = 123

• Step 1: 1 + 2 + 3 = 6.
• Step 2: 6 is one digit.
• Result: 6.

Code for Iterative Approach

Copy codeclass Solution:
    def addDigits(self, num: int) -> int:
        # Step 1: Keep going until one digit
        while num > 9:  # More than one digit
            # Step 2: Add all digits
            total = 0
            while num > 0:
                total += num % 10  # Get last digit
                num //= 10         # Remove last digit
            num = total

        # Step 3: Return the single digit
        return num

• Time Complexity: O(log n)—depends on number of digits, reduced each loop.
• Space Complexity: O(1)—just a few variables.

It’s a hands-on way to see the process unfold.

Comparing the Two Solutions

• Best Solution (Formula):
• Pros: O(1) time, super fast, no loops.
• Cons: Needs the math trick to understand.
• Alternative Solution (Iterative):
• Pros: Shows the summing process clearly.
• Cons: O(log n) time, slower for big numbers.

Formula wins for speed.

Additional Examples and Edge Cases

Zero

• 0 → 0

Single Digit

• 7 → 7

Large Number

• 999 → 9 + 9 + 9 = 27 → 2 + 7 = 9

Both handle these perfectly.

Complexity Breakdown

• Formula:
• Time: O(1)—instant answer.
• Space: O(1)—no extras.
• Iterative:
• Time: O(log n)—digit counting loops.
• Space: O(1)—minimal space.

Formula is the champ.

Key Takeaways

• Formula: Math can skip steps.
• Iterative: Loops show the journey.
• Digits: Break numbers down with % and //.
• Python Tip: Numbers are fun—see [Python Basics](/python/basics).

Final Thoughts: Sum Digits Like a Pro

LeetCode 258: Add Digits in Python is a delightful number game. The formula solution is a quick magic trick, while iterative summing walks you through each step. Want more? Try LeetCode 202: Happy Number or LeetCode 191: Number of 1 Bits. Ready to add? Head to Solve LeetCode 258 on LeetCode and crunch those digits today!