0929MediumMathCounting

Digits That Rebuild Their Factorial Total

Tracked in this browser only

Trains the technique from

LeetCode 3848Check Digitorial Permutation

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

Take each digit of n, work out its factorial, and add those factorials together. Call the result the factorial total of n, taking 0! to be 1.

Return true when the digits of the factorial total are a rearrangement of the digits of n, that is when the two numbers use exactly the same digits the same number of times.

Examples

Example 1

Input: n = 154
Output: true

The digit factorials are 1, 120 and 24, which come to 145. Those digits are a rearrangement of 1, 5 and 4.

Example 2

Input: n = 123
Output: false

The digit factorials 1, 2 and 6 come to 9, which uses a digit that 123 does not.

Example 3

Input: n = 40585
Output: true

The digit factorials 24, 1, 120, 40320 and 120 come to 40585, the number itself.

Constraints

1 <= n <= 10^9

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def is_digitorial_permutation(n: int) -> bool:

Java

public boolean isDigitorialPermutation(int n)

The intended approach

Time O(d log d) for the d digits, the sort of at most ten digits dominating.Space O(1).

There are only ten digit factorials, so work them out once into a small table and the factorial total is then one pass over the digits of `n`. Checking the rearrangement means comparing the two numbers as collections of digits rather than as numbers, since the order must not matter; sorting each one's digits and comparing the results does exactly that, and it also catches the case where the two have different lengths, because their sorted forms then differ in size.

Pythonentry point: is_digitorial_permutation

def is_digitorial_permutation(n):
    factorial = [1] * 10
    for d in range(1, 10):
        factorial[d] = factorial[d - 1] * d
    total = 0
    left = n
    while left > 0:
        total += factorial[left % 10]
        left //= 10
    return sorted(str(n)) == sorted(str(total))

The obvious version

Work out each digit's factorial by multiplying up from one every time, then compare the two collections of digits by taking the digits of one and striking them off a list of the other's, reporting a match only when nothing is left over on either side. No table and no sorting.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_is_digitorial_permutation(n):
    def factorial_of(d):
        out = 1
        for step in range(2, d + 1):
            out *= step
        return out

    total = 0
    left = n
    while left > 0:
        total += factorial_of(left % 10)
        left //= 10
    have = []
    left = n
    while left > 0:
        have.append(left % 10)
        left //= 10
    want = []
    left = total
    while left > 0:
        want.append(left % 10)
        left //= 10
    if total == 0:
        want = [0]
    for d in want:
        if d in have:
            have.remove(d)
        else:
            return False
    return len(have) == 0

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in