Start learning free

LESSON 177 OF 338 · FUNCTIONS & CLASSES

Magical Number in Go: Repeated Digit Sum with Two Functions

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: magicNumber(39) = magicNumber(3 + 9) = magicNumber(12) = magicNumber(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

    GO · FUNCTIONS & CLASSES

    Magical Number in Go, explained

    Problem overview

    The function magicNumber receives a positive integer n. Add its digits, and if the sum still has two or more digits, add the digits of the sum, and so on until one digit remains. That digit is the answer. For 39: 3 + 9 = 12, then 1 + 2 = 3, so the result is 3. For 928435: 9 + 2 + 8 + 4 + 3 + 5 = 31, then 3 + 1 = 4.

    Approach

    The task has two layers. The outer layer repeats a transformation until the number is small. The inner layer is the transformation itself, the sum of the digits of a number. Writing them as two functions keeps each one short: magicNumber assumes a helper digitSum exists, and digitSum is written afterwards.

    The outer loop is guaranteed to finish. A number with two or more digits is larger than the sum of its digits (for example 39 becomes 12), so the value strictly shrinks each round and cannot stay above 9 forever.

    Getting the digits uses arithmetic, not string conversion. The remainder of a division by 10 is the last digit, and dividing by 10 drops it, because integer division discards the remainder.

    Step by step

    magicNumber

    1. Loop while n has at least two digits, which means n > 9. Go has no while, so this is a for with only a condition.
    2. In the loop, replace n with digitSum(n).
    3. After the loop, n is a single digit. Return it.

    digitSum

    1. Declare it with an int parameter and an int result. Go lets you define it after magicNumber, since top-level functions can appear in any order.
    2. Start sum at 0 with :=.
    3. Loop while n > 0. Each pass adds n % 10 to sum, then does n /= 10.
    4. Return sum after the loop.

    Tracing digitSum(39): 39 % 10 is 9, so sum is 9 and n becomes 3. Then 3 % 10 is 3, so sum is 12 and n becomes 0. The loop ends and the function returns 12.

    The solution in Go

    func magicNumber(n int) int {
    for n > 9 {
        n = digitSum(n)
    }
    return n
}

func digitSum(n int) int {
    sum := 0
    for n > 0 {
        sum += n % 10
        n /= 10
    }
    return sum
}

    Language details worth knowing

    Go passes arguments by value, so digitSum may change its own n to 0 without affecting the caller's variable. The same applies to magicNumber: assigning to the parameter n is fine and changes only the local copy.

    The / operator on two int values truncates toward zero, so 39 / 10 is 3 and /= 10 removes the last digit. The % operator takes the sign of the dividend, so for negative input the digits would come out negative or the loop would never run. The lesson only uses positive numbers.

    for n > 9 { ... } is Go's way of writing a while loop: a for with just a condition.

    Splitting the work this way also makes testing easier. You can check digitSum alone: digitSum(39) is 12, digitSum(12) is 3, and digitSum(928435) is 31. If those are right, any mistake left is in the outer loop, and the outer loop has only three lines, so there is little left to go wrong.

    Complexity

    One call to digitSum costs O(d), where d is the number of digits, which is O(log n). After the first call the value is at most 9 times the digit count, so the later rounds work on tiny numbers, and the total is O(log n) time. Space is O(1): a few integer variables.

    Tracing the larger example

    For 928435, the first call of digitSum returns 31, which is still above 9, so the loop runs again. The second call turns 31 into 4 (3 + 1). Now 4 > 9 is false, the loop stops, and the function returns 4. Two rounds were enough, and the number of rounds stays small even for very large inputs, because every round shrinks the value dramatically.

    A shortcut, for the curious

    This result is known as the digital root, and for a positive n it equals 1 + (n-1) % 9. For 39 that is 1 + 38 % 9 = 1 + 2 = 3, and for 928435 it is 4, matching the loop. The loop version is the one to write here, because it shows the process the statement describes and doesn't depend on a number-theory fact.

    Edge cases and common mistakes

    • A single-digit input is returned immediately, because the loop condition is false at once. magicNumber(7) is 7.
    • Multiples of 9 end at 9, not 0: magicNumber(18) is 9, and so is magicNumber(99999).
    • Putting return inside the loop returns after one round, which gives 12 for input 39.
    • Using n >= 9 works for 9 too, but n > 9 states the idea precisely: more than one digit.
    • Forgetting to assign the result of digitSum(n) back to n leaves an endless loop.

    Testing

    • 39 gives 3.
    • 928435 gives 4.
    • 7 gives 7.
    • 18 gives 9.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free