You are given an integer n.
A number is called digitorial if the sum of the factorials of its digits is equal to the number itself.
Determine whether any permutation of n (including the original order) forms a digitorial number.
Return true if such a permutation exists, otherwise return false.
Note:
x, denoted as x!, is the product of all positive integers less than or equal to x, and 0! = 1.
Example 1:
Input: n = 145
Output: true
Explanation:
The number 145 itself is digitorial since 1! + 4! + 5! = 1 + 24 + 120 = 145. Thus, the answer is true.
Example 2:
Input: n = 10
Output: false
Explanation:
10 is not digitorial since 1! + 0! = 2 is not equal to 10, and the permutation "01" is invalid because it starts with zero.
Constraints:
1 <= n <= 109Problem Overview: You are given an integer n. Compute its digitorial, defined as the product of the factorials of each digit. The task is to check whether the digits of the resulting value form a permutation of the digits in n.
Approach 1: Brute Force Permutation Check (Factorial Time)
Extract the digits of n and generate every permutation of those digits. For each permutation, convert it back to a number and compare it with the computed digitorial value. If any permutation matches exactly, the condition holds. This approach directly checks the definition but quickly becomes impractical because generating permutations takes O(d!) time for d digits, with O(d) extra space for recursion or permutation storage. Useful only for very small inputs.
Approach 2: Digit Counting with Simulation (O(d + r))
Compute the digitorial by iterating through each digit of n and multiplying the corresponding factorial value. Then compare digit frequencies of the original number and the computed result. Use a fixed-size frequency array of size 10 to count occurrences of digits 0-9. If both numbers have identical digit counts, the digitorial is a permutation of the original digits. This simulation runs in O(d + r) time where d is the digit count of n and r is the digit count of the digitorial result, with O(1) space.
This approach works because permutations preserve digit frequency. Instead of generating permutations explicitly, you verify equivalence by counting digits. Factorials for digits 0–9 can be precomputed once to avoid repeated calculation. The rest is simple iteration and array updates.
Conceptually this combines basic math operations with counting techniques. The main work is digit extraction and frequency comparison, both common patterns in digit manipulation problems.
Recommended for interviews: The digit-count simulation approach. Interviewers expect you to avoid explicit permutation generation and instead compare digit frequencies. Mentioning the brute force approach shows you understand the definition, while moving to the O(d + r) counting solution demonstrates practical optimization.
According to the problem description, no matter how the digits of number n are rearranged, the sum of factorials of the digitorial number remains unchanged. Therefore, we only need to calculate the sum of factorials of each digit of number n, and check whether the permutation of digits of this sum equals the permutation of digits of n.
The time complexity is O(log n), where n is the integer given in the problem. The space complexity is O(d), where d = 10 is the length of the factorial preprocessing array.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Permutations | O(d!) | O(d) | Only for very small digit counts or when demonstrating the naive interpretation |
| Digit Counting Simulation | O(d + r) | O(1) | General case. Efficient and simple for comparing permutations |
Check Digitorial Permutation | LeetCode 3848 | Weekly Contest 490 • Sanyam IIT Guwahati • 368 views views
Watch 8 more video solutions →Practice Check Digitorial Permutation with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor