Welcome to Subscribe On Youtube

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.

  • 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);
    }
}


  • 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;
    }
};


  • @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))


  • 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)
}


  • 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;
}

All Problems

All Solutions