Check Digitorial Permutation | LeetCode 3848 | Weekly Contest 490
Check Digitorial Permutation - Video Solution
Watch 9 video solutions for Check Digitorial Permutation, a medium level problem involving Math, Counting. This walkthrough by Sanyam IIT Guwahati has 389 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- The factorial of a non-negative integer
x, denoted asx!, is the product of all positive integers less than or equal tox, and0! = 1. - A permutation is a rearrangement of all the digits of a number that does not start with zero. Any arrangement starting with zero is invalid.
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 <= 109
Approach Overview
Problem 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.
Complexity Analysis
| 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 |