Start learning free

LESSON 176 OF 347 · FUNCTIONS & CLASSES

Magical Number in C#: Repeated Digit Sums

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

    C# · FUNCTIONS & CLASSES

    Magical Number in C#, explained

    Problem overview

    The method MagicNumber takes an int, n, and keeps replacing it with the sum of its digits until only one digit is left. That final digit is the answer. For 39, the digit sum is 3 + 9 = 12, then 1 + 2 = 3, so the result is 3. For 928435, the first sum is 9 + 2 + 8 + 4 + 3 + 5 = 31 and the second is 3 + 1 = 4, so the result is 4.

    Approach: split the work into two functions

    The task combines two smaller jobs, and the lesson separates them:

    • a helper DigitSum that adds up the digits of a number once;
    • the main method MagicNumber that calls the helper over and over until the number has a single digit.

    Writing the main method first, as if the helper already existed, makes it short and easy to read. The loop always ends, because a number with two or more digits is larger than its digit sum. For example, 39 is larger than 12, so each round produces a smaller value.

    Here is DigitSum(928435) in action. Each round adds the last digit to sum and then chops it off n:

    n = 928435  sum = 0
n = 92843   sum = 5
n = 9284    sum = 8
n = 928     sum = 12
n = 92      sum = 20
n = 9       sum = 22
n = 0       sum = 31

    When n reaches 0 the loop stops and 31 is returned. MagicNumber then repeats the process on 31 and gets 4.

    The two loops have different conditions on purpose: the inner one stops at 0 because it needs every digit, while the outer one stops at a single digit, 9 or below.

    Step by step

    1. Loop while there are two or more digits. A number has at least two digits exactly when it is greater than 9, so the loop is while (n > 9).
    2. Replace n with its digit sum. n = DigitSum(n); assigns the helper's result back.
    3. Return n after the loop. Returning inside the loop would stop after the first round.
    4. Declare the helper. public int DigitSum(int n) takes an int and returns an int. It receives its own copy of n, so changing n inside it doesn't affect the caller's variable.
    5. Start a running total. int sum = 0;, because no digit has been added yet.
    6. Loop while digits remain. A positive number still has a digit left, so while (n > 0).
    7. Add the last digit. n % 10 is the remainder after division by 10, which is the last digit, so sum += n % 10;.
    8. Remove the last digit. n /= 10; divides by 10. With two int operands, / is integer division and drops the remainder, so 928435 becomes 92843.
    9. Return the sum after the loop, once every digit has been added.

    The solution in C#

    class Solution {

    public int DigitSum(int n) {
        int sum = 0;
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }

    public int MagicNumber(int n) {
        while (n > 9) {
            n = DigitSum(n);
        }
        return n;
    }
}

    The C# details behind it:

    • Integer division truncates. 39 / 10 is 3, not 3.9. That behaviour is what makes n /= 10 remove the last digit.
    • Parameters are copies. int arguments are passed by value, so DigitSum can freely destroy its n while counting. The original value stays with the caller.
    • Methods can call each other by their plain names when they belong to the same class. The order of the two methods in the file doesn't matter to the compiler.
    • Compound assignment. sum += x means sum = sum + x, and n /= 10 means n = n / 10.

    Complexity

    Time. One call to DigitSum takes one loop iteration per digit, which is O(log n), since the number of digits grows with the logarithm of the value. After the first call, the number is small: an int has at most 10 digits, so its digit sum is at most 90. The remaining rounds work on numbers of at most two digits, which makes them effectively constant. The total is O(log n).

    Space: O(1). The code uses a few int variables.

    Edge cases and common mistakes

    • Already one digit. 7 skips the loop and is returned as is.
    • Zero. MagicNumber(0) returns 0. The statement is about positive numbers, so this is only a safe fallback.
    • Negative input. The problem only uses positive numbers. A negative n fails the test n > 9, so the method would return it unchanged. If negative values were possible, you would decide what the result should be and handle them before the loop.
    • The largest int. 2147483647 sums to 46, then 10, then 1, so the result is 1. The sum of digits never overflows.
    • Using n >= 9 in the first loop. It would sum the digits of 9 itself, which gives 9 again, and the loop would never end.
    • Using / to get the last digit. The last digit comes from %. Division removes it.
    • Returning inside the loop. The method would stop after the first round, so 39 would return 12.

    Testing

    • 39 gives 3.
    • 928435 gives 4.
    • 7 gives 7.
    • 999 gives 9, since DigitSum(999) is 27 and then 9.
    • 2147483647 gives 1.

    As a side note, the same result has a closed form for positive n: 1 + (n - 1) % 9. The loop version is what the lesson asks for, and it is the one that shows how to take apart the digits of a number.

    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free