Skip to main content
Talentd

Check Digitorial Permutation - Solution & Explanation

MediumMathCounting6 min readAsked at: Bloomberg
Practice this problem

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 as x!, is the product of all positive integers less than or equal to x, and 0! = 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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force PermutationsO(d!)O(d)Only for very small digit counts or when demonstrating the naive interpretation
Digit Counting SimulationO(d + r)O(1)General case. Efficient and simple for comparing permutations

Video Solution

Check Digitorial Permutation | LeetCode 3848 | Weekly Contest 490 ā€¢ Sanyam IIT Guwahati ā€¢ 389 views views

Watch 8 more video solutions ā†’

Frequently Asked Questions

Is Check Digitorial Permutation easy or hard?
Check Digitorial Permutation is generally classified as a medium difficulty problem. The main challenge is recognizing that permutation comparison can be reduced to digit frequency counting instead of generating all permutations.
Check Digitorial Permutation Python/Java solution
Most implementations simulate the process: iterate through digits, multiply their factorial values, and compare digit counts using arrays or hash maps. The same logic translates easily across Python, Java, C++, Go, and TypeScript.
How to solve Check Digitorial Permutation in O(n)?
Treat n as the number of digits. Iterate through the digits once to compute the digitorial using precomputed factorials. Then build digit frequency counts for both numbers and compare them. Matching counts confirm that the digitorial value is a permutation of the original digits.
What is the best approach for Check Digitorial Permutation?
The most efficient approach uses digit counting. Compute the digitorial by multiplying factorials of each digit, then compare digit frequencies between the original number and the result. This avoids generating permutations and runs in O(d + r) time with constant space.
Is Check Digitorial Permutation asked at Google/Amazon/Meta?
Problems involving digit manipulation, factorial-based transformations, and permutation checks frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test counting techniques and efficient handling of digit-based math operations.
What data structure is used in Check Digitorial Permutation?
A fixed-size frequency array (size 10) is typically used to count digit occurrences. This allows constant-time updates and fast comparison between the digit distributions of the original number and the computed digitorial.
What is the time complexity of Check Digitorial Permutation?
The optimal simulation approach runs in O(d + r) time, where d is the number of digits in the input number and r is the number of digits in the digitorial result. Space complexity remains O(1) because only a fixed-size digit frequency array of size 10 is required.

Ready to solve this problem?

Practice Check Digitorial Permutation with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer