LeetCode 3848 - Check Digitorial Permutation

Difficulty: 🟡 Medium
Topics: Math, Counting

Solution

Problem Understanding

The problem asks us to determine whether any permutation of the digits of a given integer n forms a digitorial number. A digitorial number is defined as a number equal to the sum of the factorials of its digits. For instance, 145 is digitorial because $1! + 4! + 5! = 145$.

The input is a single integer n in the range $1 \le n \le 10^9$, which means we may have up to 10 digits. The output is a boolean value: true if some permutation of the digits (including the original order) forms a digitorial number, and false otherwise. Importantly, any permutation starting with zero is invalid.

Key constraints and insights are:

Factorials grow very quickly. The largest single-digit factorial is $9! = 362880$. This means even with 10 digits, the sum of their factorials cannot exceed $10 \times 362880 = 3628800$, which is far smaller than the largest 10-digit number ($10^9$). So we never need to consider numbers larger than a few million.
Permutations starting with zero are invalid, so we can ignore combinations where the leading digit is 0.
Since factorial sums are independent of digit order, the problem reduces to checking whether the sum of factorials of digits equals any number formed by a permutation of those digits. This is equivalent to checking if the sum of factorials equals n itself (because rearranging digits does not change the factorial sum) or any rearrangement of those digits that forms a valid number.

Edge cases include:

Single-digit numbers. Only 1 and 2 are digitorial (1! = 1, 2! = 2).
Numbers containing 0. Permutations with leading zeros are invalid.
Large numbers (close to $10^9$). These cannot form digitorials because the sum of factorials of up to 10 digits is far less than $10^9$.

Approaches

Brute Force

A naive approach would generate all permutations of the digits of n, check for each permutation if it starts with a non-zero digit, and then compute the sum of factorials of the digits to see if it equals the permutation itself. While correct, this is extremely inefficient because a 10-digit number has $10! = 3,628,800$ permutations. Factorial computations for each permutation make this approach impractical.

Optimal Approach

The key insight is that the sum of the factorials of digits is independent of their order. Therefore, instead of generating permutations, we can simply compute the sum of factorials of the digits of n and check if the sum is a permutation of the digits of n.

A number is a permutation of the original if they have the same digit counts. This can be efficiently checked using a frequency map of digits. In short:

Precompute factorials of digits 0-9.
Compute the sum of factorials of the digits of n.
Check if the sum has the same digit counts as n and does not start with 0.

This avoids generating all permutations explicitly.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(d! * d)	O(d)	Generate all permutations and check factorial sums
Optimal	O(d)	O(d)	Compute factorial sum and check digit frequency; d = number of digits

Algorithm Walkthrough

Precompute factorials for digits 0 to 9 in an array for O(1) lookup.
Convert n into a string or array of digits.
Compute factorial_sum by summing the factorials of each digit.
If factorial_sum has a different number of digits than n, return false immediately.
Count the frequency of each digit in n.
Count the frequency of each digit in factorial_sum.
Compare the two frequency maps. If they match, return true. Otherwise, return false.

Why it works: The factorial sum is invariant under digit permutation, so if a valid permutation exists that equals the sum, the sum itself must be a permutation of n. By comparing digit counts, we guarantee that the sum can be formed by rearranging the original digits.

Python Solution

class Solution:
    def isDigitorialPermutation(self, n: int) -> bool:
        from collections import Counter
        
        # Precompute factorials of digits 0-9
        factorial = [1] * 10
        for i in range(1, 10):
            factorial[i] = factorial[i - 1] * i
        
        digits = [int(d) for d in str(n)]
        factorial_sum = sum(factorial[d] for d in digits)
        
        # Convert sum to string for digit frequency comparison
        sum_digits = str(factorial_sum)
        
        # Leading zero check
        if sum_digits[0] == '0':
            return False
        
        # Compare digit frequencies
        return Counter(sum_digits) == Counter(str(n))

Explanation:

The code first computes factorials for digits 0-9 to avoid repeated computation. It converts n to a list of digits, computes the sum of factorials, and converts the sum to a string. Leading zero check ensures invalid permutations are rejected. Finally, it compares digit counts using Counter to verify whether any permutation of n matches the factorial sum.

Go Solution

package main

import (
    "strconv"
)

func isDigitorialPermutation(n int) bool {
    factorial := [10]int{1,1,2,6,24,120,720,5040,40320,362880}
    
    digits := strconv.Itoa(n)
    factorialSum := 0
    for _, d := range digits {
        factorialSum += factorial[int(d - '0')]
    }
    
    sumStr := strconv.Itoa(factorialSum)
    if sumStr[0] == '0' {
        return false
    }
    
    countDigits := func(s string) [10]int {
        var count [10]int
        for _, c := range s {
            count[int(c-'0')]++
        }
        return count
    }
    
    return countDigits(digits) == countDigits(sumStr)
}

Go-specific notes: We use fixed-size arrays instead of hash maps for digit counts since digits are in range 0-9. The factorial array is precomputed. String conversion is used for both n and the factorial sum to count digits efficiently.

Worked Examples

Example 1: n = 145

Step	Value
digits	[1,4,5]
factorial_sum	1! + 4! + 5! = 1 + 24 + 120 = 145
sum_digits	"145"
Counter comparison	Counter("145") == Counter("145") → True

Example 2: n = 10

Step	Value
digits	[1,0]
factorial_sum	1! + 0! = 1 + 1 = 2
sum_digits	"2"
Length mismatch	2 digits vs 1 digit → False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(d)	Convert `n` to digits and sum factorials; compare digit counts, d = number of digits
Space	O(d)	Store digits and count arrays or Counter objects

Since d <= 10 for n ≤ 10^9, the algorithm is effectively O(1) in practice.

Test Cases

# Provided examples
assert Solution().isDigitorialPermutation(145) == True  # 145 itself
assert Solution().isDigitorialPermutation(10) == False  # no valid permutation

# Edge cases
assert Solution().isDigitorialPermutation(1) == True    # single digit, digitorial
assert Solution().isDigitorialPermutation(2) == True
assert Solution().isDigitorialPermutation(40585) == True # known digitorial
assert Solution().isDigitorialPermutation(0) == False   # 0 is invalid
assert Solution().isDigitorialPermutation(9999999) == False  # too large for factorial sum
assert Solution().isDigitorialPermutation(123) == False # sum factorial != permutation

Test	Why
145	Tests normal digitorial detection
10	Tests invalid permutation due to leading zero
1, 2	Single-digit edge cases
40585	Tests larger known digitorial number
0	Edge case for zero, invalid
9999999	Stress test for large numbers
123	Negative case where sum doesn't match permutation

Edge Cases

Single-digit numbers: Only 1 and 2 are digitorials. Any other single-digit number will fail. Implementation handles this naturally because the factorial sum is computed and compared to the same number.
Numbers containing zero: Any permutation with a leading zero is invalid. For example, 10 cannot rearrange to form 01. The solution explicitly checks if the first digit of the factorial sum string is zero.
Large numbers exceeding factorial sum capacity: Numbers like 999999999