Skip to content

3848. Check Digitorial Permutation

Description

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

Solutions

Solution 1: Simulation

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
@cache
def f(x: int) -> int:
    if x < 2:
        return 1
    return x * f(x - 1)

class Solution:
    def isDigitorialPermutation(self, n: int) -> bool:
        x, y = 0, n
        while y:
            x += f(y % 10)
            y //= 10
        return sorted(str(x)) == sorted(str(n))

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    private static final int[] f = new int[10];

    static {
        f[0] = 1;
        for (int i = 1; i < 10; i++) {
            f[i] = f[i - 1] * i;
        }
    }

    public boolean isDigitorialPermutation(int n) {
        int x = 0;
        int y = n;

        while (y > 0) {
            x += f[y % 10];
            y /= 10;
        }

        char[] a = String.valueOf(x).toCharArray();
        char[] b = String.valueOf(n).toCharArray();

        Arrays.sort(a);
        Arrays.sort(b);

        return Arrays.equals(a, b);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    bool isDigitorialPermutation(int n) {
        static int f[10];
        static bool initialized = false;

        if (!initialized) {
            f[0] = 1;
            for (int i = 1; i < 10; i++) {
                f[i] = f[i - 1] * i;
            }
            initialized = true;
        }

        int x = 0;
        int y = n;

        while (y > 0) {
            x += f[y % 10];
            y /= 10;
        }

        string a = to_string(x);
        string b = to_string(n);

        sort(a.begin(), a.end());
        sort(b.begin(), b.end());

        return a == b;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func isDigitorialPermutation(n int) bool {
    f := make([]int, 10)
    f[0] = 1
    for i := 1; i < 10; i++ {
        f[i] = f[i-1] * i
    }

    x := 0
    y := n

    for y > 0 {
        x += f[y%10]
        y /= 10
    }

    a := []byte(strconv.Itoa(x))
    b := []byte(strconv.Itoa(n))

    sort.Slice(a, func(i, j int) bool { return a[i] < a[j] })
    sort.Slice(b, func(i, j int) bool { return b[i] < b[j] })

    return string(a) == string(b)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function isDigitorialPermutation(n: number): boolean {
    const f: number[] = new Array(10);
    f[0] = 1;
    for (let i = 1; i < 10; i++) {
        f[i] = f[i - 1] * i;
    }

    let x = 0;
    let y = n;

    while (y > 0) {
        x += f[y % 10];
        y = Math.floor(y / 10);
    }

    const a = x.toString().split('').sort().join('');
    const b = n.toString().split('').sort().join('');

    return a === b;
}

Comments