LESSON 177 OF 348 · FUNCTIONS & CLASSES

Magical Number in TypeScript: 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

Guided

Ctrl + Enter to check

TYPESCRIPT · FUNCTIONS & CLASSES

Magical Number in TypeScript, explained

Problem overview

A magical number is what you get from a positive number by adding its digits again and again until one digit is left. The method magicNumber receives a number n and returns that single digit.

For n = 39, the digits add up to 3 + 9 = 12, which still has two digits. Adding again gives 1 + 2 = 3, so the answer is 3. For n = 928435, the first sum is 9 + 2 + 8 + 4 + 3 + 5 = 31, and the second is 3 + 1 = 4, so the answer is 4.

Approach: two small loops

The problem splits into two parts that are easy to write separately:

A digit sum: given a number, add up its digits.
A repeat: keep replacing the number with its digit sum until it has one digit.

The lesson writes the repeating part first, pretending that a method digitSum already exists, and then writes digitSum. This is a useful habit: decide what the helper must do, use it, and fill it in afterwards.

The repeating loop must end. A number with at least two digits is larger than its digit sum, so every pass makes n strictly smaller, and a positive whole number can't shrink forever.

To get the digits of a number, look at its last digit and then drop it. The remainder after dividing by 10 is the last digit: 39 % 10 is 9. Dividing by 10 and keeping the whole-number part drops that digit: 39 divided by 10 is 3.9, and its whole part is 3. Repeat until nothing is left.

Step by step

First, magicNumber:

Loop while n has two or more digits. That is the same as n > 9.
Replace n by its digit sum. Call this.digitSum(n) and assign the result back to n. The call goes through this because digitSum is a method of the class.
Return n after the loop. At that point it has one digit. The return belongs after the loop. Inside it, the method would stop after the first pass.

Then digitSum, written above magicNumber in the class:

Declare the method with a parameter n of type number and the return type number. Class methods are written without the function keyword.
Start the total. Declare sum with let and the type number, set to 0. No digit has been added yet, and the value changes on every pass.
Loop while digits remain. A positive number still has a digit exactly when n > 0.
Add the last digit: sum += n % 10.
Drop the last digit: n = Math.floor(n / 10). In TypeScript, / on numbers gives a fraction when the division is not exact, as in 39 / 10 being 3.9. Math.floor rounds down to the whole part.
Return sum after the loop.

The solution in TypeScript

class Solution {
    digitSum(n: number): number {
        let sum: number = 0;
        while (n > 0) {
            sum += n % 10;
            n = Math.floor(n / 10);
        }
        return sum;
    }

    magicNumber(n: number): number {
        while (n > 9) {
            n = this.digitSum(n);
        }
        return n;
    }
}

The TypeScript details worth a closer look:

No integer division. A number is a double-precision float, so 39 / 10 is 3.9, not 3. Without Math.floor, n would never reach 0 exactly, and the loop would carry on through ever smaller fractions. For positive numbers, Math.trunc would do the same job as Math.floor.
% is the remainder. For positive whole numbers, n % 10 is the last digit. For negative numbers the remainder keeps the sign of n, which is one more reason the problem sticks to positive input.
Parameters can be reassigned. Both methods change their parameter n. That only changes the method's own copy. The caller's variable, since a number is passed by value, is untouched.
this.digitSum. Inside a method, a bare digitSum(n) would look for a function outside the class and fail to compile. this.digitSum finds the method on the same object. Calling it as new Solution().magicNumber(39) makes this the new object.
Precision limit. Whole numbers are exact only up to 2 to the power 53, about 9 quadrillion, so for larger values the digits themselves can be wrong. Typical inputs stay far below that.

Complexity

Let d be the number of digits of n, which is about the base-10 logarithm of n.

Time: O(d) in practice. The first digitSum call takes d steps. The result is at most 9 times d, so it has far fewer digits than that, and every later call is on a far shorter number. The first pass dominates, so the total is O(d), that is, O(log n).

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

Edge cases and common mistakes

Already one digit. 5 skips the loop and is returned as it is.
Multiples of 10. 10 becomes 1 in one pass.
Forgetting Math.floor. n / 10 keeps the fraction, so 39 becomes 3.9, then 0.39, and so on. The loop keeps running for hundreds of passes until the value underflows to 0, and the sum it returns is wrong.
Loop condition n >= 9. It is wrong for 9: the digit sum of 9 is 9, so the loop would never end.
Returning inside a loop. A return inside the first loop ends magicNumber after one digit sum, which only works when that sum has one digit.
Calling the helper without this. digitSum(n) fails to compile inside the class.

Testing

39 gives 3.
928435 gives 4.
5 gives 5.
10 gives 1.
99 gives 9.

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

Start learning free