Найдите минимальное число X такое, что сумма факториала его цифр равна N

Для заданного числа N задача состоит в том, чтобы найти минимальное число X такое, что A(X) = N , где A(X) для натурального числа X представляет собой сумму факториалов его цифр. Например, А(154) = 1! + 5! + 4!= 145. Вернуть список цифр, представляющих число X.

Пример:

Input: N = 40321
Output: 18
Explanation: A(18) =1! + 8!  = 40321. Note that A(80) and A(81) are also 40321, But 18 is the smallest number.

Input: N = 5040
Output: 7

Подход: Чтобы решить проблему, следуйте следующей идее:

For any digit n, n! can be written as n * ((n – 1)!). So, digit n – 1 is required exactly n times. This means that taking smaller numbers when a larger number can be taken will just increase the number of digits in our final answer. So, use the greedy approach and subtract the largest value of n! from N until N becomes 0.

Следуйте инструкциям, чтобы решить эту проблему:

• Составьте массив факториалов и поместите в него все факториалы от 0 до 9.
• Сохраните переменную i и инициализируйте ее значением 9.
• Теперь запустите цикл while и проверьте, является ли factorial[i] <= N.
• Теперь запустите еще один цикл while и проверьте, сколько раз вы можете вычесть factorial[i] из N. Сделайте это для i от 9 до 1.
• Теперь просто переверните вектор, чтобы получить наименьшее возможное число.

Ниже приведена реализация этого подхода:

Временная сложность : O (log (N))
Вспомогательное пространство: O(1), поскольку мы создаем только один факторный вектор размера 10.