LESSON 206 OF 414 · FUNCTIONS & CLASSES

Magical Number in Rust: Repeated Digit Sums with a Helper

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

Guided

Ctrl + Enter to check

RUST · FUNCTIONS & CLASSES

Magical Number in Rust, explained

Problem overview

The function magic_number takes a positive i32 and adds its digits. If the sum still has more than one digit, it adds the digits of the sum, and it repeats until a single digit remains. That digit is the result.

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

Approach: split the work in two

The task has two layers. The inner layer is "add up the digits of a number". The outer layer is "do that again and again until one digit is left". Keeping them in separate functions makes each one small.

The outer loop is safe because a number with two or more digits always shrinks when its digits are added. 39 becomes 12, and 99 becomes 18. The value gets smaller on every round, and it can't go below 1 for a positive number, so the loop must stop.

For the inner layer, two integer operations peel digits off a number. n % 10 is the last digit, and n / 10 is the number with that last digit removed, because dividing two integers in Rust drops the fractional part. Repeating both until n reaches 0 visits every digit once.

Step by step

The lesson writes magic_number first, assumes the helper exists, and then writes the helper.

Loop while n has at least two digits. A number has two or more digits exactly when it is greater than 9, so the condition is n > 9. The parameter is declared mut n so the function may reassign it.
Replace n by its digit sum. Inside the loop, call Self::digit_sum(n) and assign the result back to n. The helper lives in the same impl block and takes no self, so it is called through Self::.
Return n after the loop. It is the function's last expression, with no semicolon. Returning inside the loop would stop after the first round.
Write digit_sum above magic_number. It takes an i32 and returns an i32. The parameter is declared mut n because the function strips digits off its own copy of the number. The caller's variable is not affected.
Declare sum with let mut, starting at 0. Rust infers i32 from how it is used.
Loop while digits remain. A number still has a digit left exactly when it is greater than 0.
Add the last digit: sum += n % 10.
Remove the last digit: n /= 10.
Return sum after the loop, again as a final expression.

Tracing digit_sum(39): n is 39, so sum becomes 9 and n becomes 3. Then sum becomes 12 and n becomes 0, and the loop ends. The result is 12. A second round, digit_sum(12), gives 3.

The solution in Rust

impl Solution {
    fn digit_sum(mut n: i32) -> i32 {
        let mut sum = 0;
        while n > 0 {
            sum += n % 10;
            n /= 10;
        }
        sum
    }

    fn magic_number(mut n: i32) -> i32 {
        while n > 9 {
            n = Self::digit_sum(n);
        }
        n
    }
}

Rust details worth knowing:

mut on a parameter. Parameters are immutable by default. Without mut, n /= 10 fails with "cannot assign to immutable argument n". The keyword only affects the function's own copy: an i32 is copied into the call, so the caller's value stays the same.
The final expression. sum and n on their own lines have no semicolon, so they are the return values. Writing sum; turns the line into a statement, the function then ends with no value, and the compiler reports mismatched types: it expected i32 and found ().
Self::digit_sum. Calling a function of the same impl block by its bare name does not compile: the compiler says it cannot find the function in this scope and suggests Self::.
Integer division. / on two i32 values gives an i32, discarding the remainder, so 12 / 10 is 1. No casting or rounding call is needed.
No overflow here. The digit sum of any i32 is below 100 (1999999999 gives 82), so the sums are always small.

Complexity

Let d be the number of digits of n.

Time: O(d) for the first round. digit_sum removes one digit per pass, so it makes d passes. After that the number is at most 9 * d, so the later rounds are far cheaper. For an i32, d is at most 10, so the whole function does a handful of operations.

Space: O(1). A few integers, no recursion and no collections.

Edge cases and common mistakes

Already one digit. n = 7 fails the condition n > 9, so the loop never runs and the function returns 7.
Exactly 10. digit_sum(10) is 1, so the answer is 1. The loop condition is n > 9, not n > 10.
A sum that is still two digits. 99 gives 18, which gives 9. This is why the outer function loops instead of calling digit_sum once.
The largest i32. 2147483647 becomes 46, then 10, then 1.
Zero and negative numbers. The problem promises a positive number. For 0 the function returns 0, and for a negative number both loops are skipped, so it returns the number unchanged. In digit_sum, the condition n > 0 would also stop at once for a negative input.
Returning inside the loop. It would stop after the first digit sum, so 99 would give 18.
Using n >= 0 in digit_sum. Because n reaches 0 and 0 / 10 is 0, the loop would never end.

There is also a closed form for positive numbers, 1 + (n - 1) % 9, which gives the same answers in constant time. The loop version is the one this lesson practises.

Testing

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

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

Start learning free