Start learning free

LESSON 204 OF 415 · FUNCTIONS & CLASSES

Magical Number in Swift: Repeated Digit Sums 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: 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 11
    Ctrl + Enter to check

    SWIFT · FUNCTIONS & CLASSES

    Magical Number in Swift, explained

    Problem overview

    A magical number comes from a positive integer by adding its digits, then adding the digits of that sum, and so on until one digit is left. The method magicNumber(_ n: Int) -> Int returns that digit.

    For 39: 3 + 9 = 12, then 1 + 2 = 3, so the answer is 3. For 928435: 9 + 2 + 8 + 4 + 3 + 5 = 31, then 3 + 1 = 4, so the answer is 4.

    Approach: split the work into two functions

    There are two jobs here: adding the digits of a number, and repeating that until the number is small. Each is easy alone, so the lesson writes two functions. digitSum adds the digits of a number. magicNumber calls it in a loop while the number still has two or more digits.

    To take digits off a number, use two integer operations. n % 10 is the last digit, and n / 10 is the number without it, because integer division drops the remainder. Repeating both until nothing is left visits every digit once. For 928435: the digits come out as 5, 3, 4, 8, 2, 9 and the sum is 31.

    The loop in magicNumber always ends. A number with two or more digits is larger than its digit sum, so the value shrinks on each pass until it falls to a single digit.

    Step by step

    The lesson first writes magicNumber, assuming digitSum exists, and then writes digitSum.

    1. Make a mutable copy of the parameter. A Swift parameter is a constant, so n cannot be reassigned. Declare var n = n; the new n shadows the parameter for the rest of the function.
    2. Loop while n has two digits or more. That means n > 9.
    3. Replace n by its digit sum with n = digitSum(n).
    4. Return n after the loop, when it is a single digit.
    5. Declare digitSum. It takes an Int with no argument label (_) and returns an Int, so callers write digitSum(n).
    6. Copy the parameter with var n = n, as before, because the function will strip digits from n.
    7. Declare sum as a var starting at 0.
    8. Loop while a digit remains, that is, while n > 0.
    9. Add the last digit with sum += n % 10.
    10. Remove the last digit with n /= 10.
    11. Return sum once the loop ends.

    The solution in Swift

    class Solution {
    func digitSum(_ n: Int) -> Int {
        var n = n
        var sum = 0
        while n > 0 {
            sum += n % 10
            n /= 10
        }
        return sum
    }
    func magicNumber(_ n: Int) -> Int {
        var n = n
        while n > 9 {
            n = digitSum(n)
        }
        return n
    }
}

    The Swift details worth a closer look:

    • Shadowing a parameter. var n = n is legal and common: the right side is the parameter, and the left side is a new variable with the same name. Assigning to the parameter directly, n = 3, is a compile error ("cannot assign to value: 'n' is a 'let' constant").
    • Integer division. With two Int operands, / truncates toward zero, so 928435 / 10 is 92843. The remainder operator % takes the sign of the left operand. Both are exact for the positive numbers in this lesson.
    • The label _. Without it, the call would have to read digitSum(n: n).
    • Method order. Inside a class, methods can call each other in any order, so magicNumber may call digitSum whichever comes first in the file. Both are called on the same instance without any prefix.

    A shortcut, and why the lesson does not use it

    Repeated digit sums have a known pattern: for a positive n the result is 1 + (n - 1) % 9. It works because a number and its digit sum leave the same remainder when divided by 9, and it needs no loop at all. The lesson writes the loops on purpose, to practise splitting a task into functions and taking digits with % and /. Both give 3 for 39 and 4 for 928435.

    Complexity

    Let d be the number of digits of n.

    Time: O(d), which is O(log n). The first call to digitSum takes d steps. After it, the number is at most 9 times d, so it has about log d digits, and every later pass is far cheaper. The first pass dominates.

    Space: O(1). Only a few integers are used, and there is no recursion.

    Edge cases and common mistakes

    • Already one digit. 9 skips the loop and returns 9. 0 returns 0.
    • Multiples of ten. 10 becomes 1, and 99 becomes 18 and then 9.
    • The largest Int. 9223372036854775807 has 19 digits and returns 7. The digit sum is far smaller than the number, so nothing overflows.
    • Using n >= 9 or n > 10. The first never ends, because the digit sum of 9 is 9, so n stays 9 and the condition stays true. The second skips 10 and returns 10 instead of 1.
    • Using n > 1 in digitSum. A leading digit of 1 would never be added, so 10 would give 0. The loop must run while n > 0.
    • Returning inside a loop. The return belongs after the loop, or the function ends after one pass.
    • Negative input. The lesson guarantees positive numbers. For a negative n neither loop runs, and the method returns the number unchanged.

    Testing

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