Start learning free

LESSON 199 OF 410 · FUNCTIONS & CLASSES

Magical Number in Python: Repeated Digit Sum

Practice O(log n) Read the full explanation

A magical number is obtained from a positive number by adding its digits repeatedly until we obtain one digit.

Example 1:

Input: N = 39
Output: 3
Explanation: 39 → 3 + 9 = 12 → 1 + 2 = 3

Example 2:

Input: N = 928435
Output: 4
Explanation: 9 + 2 + 8 + 4 + 3 + 5 = 31 → 3 + 1 = 4

STEP 1 OF 9
    Ctrl + Enter to check

    PYTHON · FUNCTIONS & CLASSES

    Magical Number in Python, explained

    Problem overview

    A magical number comes from a positive integer n by adding its digits, then adding the digits of that sum, and so on until only one digit is left. The method magicNumber returns that single digit.

    For n = 39, the digits add to 3 + 9 = 12. That still has two digits, so add again: 1 + 2 = 3. The answer is 3. For n = 928435, 9 + 2 + 8 + 4 + 3 + 5 = 31, then 3 + 1 = 4, so the answer is 4.

    A different meaning of "magic number"

    In everyday Python, a "magic number" usually means something else: a literal value in the code with no name, such as if age > 18, where a reader has to guess what 18 stands for. The fix is a named constant like ADULT_AGE = 18. This lesson is about a different idea: the number you get by adding digits repeatedly. In maths it is called the digital root.

    Approach: split the work into two small jobs

    The task has two parts, and each is easy by itself:

    1. Add up all the digits of a number. This is the helper digitSum.
    2. Repeat that until the number has one digit. This is the loop in magicNumber.

    The repeating loop terminates because the digit sum of a number with two or more digits is always smaller than the number. For 39 the sum is 12, and for 12 the sum is 3. The value strictly decreases, and it cannot go below 1 for a positive input, so the loop ends.

    Getting the digits with % and //

    Python has no direct way to loop over the digits of an integer, but two operators do the job. n % 10 is the last digit, and n // 10 is the number with the last digit removed:

    n = 39
print(n % 10)   # 9
print(n // 10)  # 3
print(divmod(39, 10))  # (3, 9)

    Repeating this until nothing is left visits every digit, starting from the last.

    Step by step

    1. Write the outer loop first, as while n > 9. A number has two or more digits exactly when it is greater than 9.
    2. Replace n with its digit sum inside the loop: n = self.digitSum(n). The helper is a method of the class, so it is called through self.
    3. Return n after the loop. It is the one-digit result. A return inside the loop would stop after the first round.
    4. Write digitSum as a method that takes self and n.
    5. Start a running total at 0, because no digit has been added yet.
    6. Loop while n > 0, that is, while the number still has a digit.
    7. Add the last digit with n % 10.
    8. Remove the last digit with n //= 10.
    9. Return the total after the loop.

    The solution in Python

    class Solution:

    def digitSum(self, n):
        sum = 0
        while n > 0:
            sum += n % 10
            n //= 10
        return sum
    
    def magicNumber(self, n: int) -> int:
        while n > 9:
            n = self.digitSum(n)
        return n

    Python details to notice:

    • Use //=, not /=. The / operator always gives a float, so 39 / 10 is 3.9, and the fractions would leak into the total. Starting from 39, a version with n /= 10 returns 13.333333333333332 instead of 12. Floor division keeps everything an integer.
    • The name sum hides a built-in. Python already has a function called sum. Inside digitSum the local variable replaces it, which is harmless here because the built-in is never called. In other code, calling sum([1, 2]) after assigning sum = 0 fails with 'int' object is not callable. A name such as total avoids the problem.
    • Integers have no size limit. The method also works for a number with 25 digits, where a language with 64-bit integers would overflow.
    • A string-based shortcut exists. sum(int(c) for c in str(n)) also gives the digit sum, for example 31 for 928435. The arithmetic version here avoids creating strings, and it is the pattern to learn.

    Complexity

    Time. digitSum takes one step per digit, so O(d) for a number with d digits, which is about log n. After the first round the number is at most 9 times the digit count, so it is tiny: a 12-digit number becomes at most 108. The later rounds cost a few steps each, so the whole method is O(log n) for practical purposes.

    Space: O(1). Only a few integer variables are used.

    A shortcut from number theory

    The magical number follows a pattern. For a positive n it equals 1 + (n - 1) % 9. Adding digits does not change a number's remainder when divided by 9, so the repeated digit sum always lands on the digit with the same remainder, using 9 instead of 0. For 39 this gives 1 + 38 % 9 = 3, and for 928435 it gives 4. The formula runs in constant time, but the lesson asks for the loops to practise while and helper methods.

    Edge cases and common mistakes

    • Already one digit. For n = 7 the outer loop never runs, and the method returns 7.
    • Multiples of 9. Both 9 and 99 give 9, not 0. The sum of digits of a positive number is never 0.
    • Numbers that need several rounds. 999999999999 becomes 108, then 9. The outer loop is needed, and one call to digitSum is not enough.
    • Zero. The statement is about positive numbers. For 0 the method returns 0, because the loop does not run.
    • Using n > 10. That stops too early on 10, which has two digits. The right test is n > 9.

    Testing

    • magicNumber(39) returns 3.
    • magicNumber(928435) returns 4.
    • magicNumber(10) returns 1.
    • magicNumber(99) returns 9.
    • magicNumber(7) returns 7.
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free