LESSON 177 OF 348 · FUNCTIONS & CLASSES

Magical Number in Kotlin: Repeated Digit Sum with while Loops

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

Guided

Ctrl + Enter to check

KOTLIN · FUNCTIONS & CLASSES

Magical Number in Kotlin, explained

Problem overview

The function magicNumber receives a positive integer n. It adds up the digits of n, then adds up the digits of that sum, and keeps going until a single digit remains. That digit is the answer.

In the first example, 39 becomes 3 + 9 = 12, then 1 + 2 = 3, so the result is 3. In the second, 928435 becomes 9 + 2 + 8 + 4 + 3 + 5 = 31, then 3 + 1 = 4, so the result is 4.

Approach: two small loops

The problem splits into two jobs, and each one is a short loop.

Outer job: as long as the number has two or more digits, replace it by its digit sum.
Inner job: compute the digit sum of a number.

The lesson writes the outer job first and assumes a function digitSum exists. This is a useful habit: decide what you need from a helper before you write it. The helper is then built to match.

The digit sum itself uses two integer operations. n % 10 is the last digit, and n / 10 removes it, because integer division drops the remainder. Repeating until the number reaches 0 visits every digit once. For 928435, the last digits come out as 5, 3, 4, 8, 2, 9.

The outer loop always ends. For any number of two or more digits, the digit sum is smaller than the number, so the value strictly decreases until it falls to a single digit.

Step by step

Make n changeable. Kotlin parameters are read-only. The line var n = n creates a local variable with the same name that starts with the parameter's value and can be reassigned.
Loop while n has two or more digits. That is exactly when n > 9.
Replace n by its digit sum: n = digitSum(n).
Return n after the loop. Returning inside the loop would stop after the first round.
Write digitSum(n: Int): Int with the same var n = n line, for the same reason.
Start sum at 0 as a var, because nothing has been added yet and the value changes on each pass.
Loop while n > 0, that is, while at least one digit is left.
Add the last digit with sum += n % 10.
Remove the last digit with n /= 10. Dividing two Int values in Kotlin gives an Int, so 928435 / 10 is 92843.
Return sum after the loop.

Tracing an example

Here is magicNumber(928435) as the program runs it. The outer loop sees n = 928435, which is greater than 9, so it calls digitSum. Inside, the inner loop takes the last digit and removes it, again and again:

n = 928435  last digit 5  sum = 5
n = 92843   last digit 3  sum = 8
n = 9284    last digit 4  sum = 12
n = 928     last digit 8  sum = 20
n = 92      last digit 2  sum = 22
n = 9       last digit 9  sum = 31
n = 0       loop ends, digitSum returns 31

The outer loop now holds n = 31, still above 9, so it calls digitSum(31), which returns 4. The check 4 > 9 fails, and the function returns 4.

The solution in Kotlin

class Solution {
    fun digitSum(n: Int): Int {
        var n = n
        var sum = 0
        while (n > 0) {
            sum += n % 10
            n /= 10
        }
        return sum
    }

    fun magicNumber(n: Int): Int {
        var n = n
        while (n > 9) {
            n = digitSum(n)
        }
        return n
    }
}

Kotlin details worth knowing:

Shadowing. var n = n declares a new variable that hides the parameter inside the function body. The compiler warns about the shadowing, but the code is valid, and the right-hand n is the parameter. The caller's value is never touched, since an Int is passed by value.
Compound assignment. sum += n % 10 and n /= 10 are shorthand for sum = sum + n % 10 and n = n / 10. The % operator binds tighter than +=, so the remainder is computed first.
Integer division truncates. 7 / 10 is 0, not 0.7. That is what makes the last step of the digit loop, from a single digit to 0, work.
Member functions can call each other. magicNumber calls digitSum by name, without any prefix. Their order inside the class doesn't matter.

A shortcut for the curious

For a positive n, the repeated digit sum equals 1 + (n - 1) % 9, a result from number theory about remainders after division by 9. It gives the answer in constant time. The loops in this lesson are the better way to learn: they work from the definition and practise while loops and helper functions.

Complexity

Time: O(log n). A number n has about log₁₀(n) digits, and one call to digitSum does a constant amount of work per digit. After the first call the value is small: an Int has at most 10 digits, so its digit sum is at most 90. Every later round works on a one- or two-digit number and takes only a few steps.

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

Edge cases and common mistakes

A single digit. 7 skips the outer loop and returns 7.
Multiples of 9. 99 becomes 18, then 9. The answer for any positive multiple of 9 is 9, never 0.
Powers of 10. 1000 has digit sum 1. The zeros contribute nothing.
Largest Int. Int.MAX_VALUE, 2147483647, has the digit sum 46, then 10, then 1, so magicNumber returns 1. No overflow happens, since digit sums are small.
Zero. The statement is about positive numbers. With 0, both loops are skipped and the function returns 0.
Using n >= 9 in the outer loop. For 9 the digit sum is 9 again, so the loop never ends. Use n > 9.
Returning inside the loop. The function would return after one round, giving 12 for 39.
Declaring sum with val. The compiler rejects sum += ... on a val.

Testing

39 gives 3.
928435 gives 4.
7 gives 7.
99 gives 9.
1000 gives 1.
2147483647 gives 1.

Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free