Fact Digit Sum

Easy

0/40

Average time to solve is 15m

Contributed by

6 upvotes

Asked in company

Problem statement

Given a positive integer ‘N’. You need to find the smallest positive integer ‘X’ such that the sum of the factorial of its digit is equal to ‘N’.

For Example:

Consider ‘N’ = 7,  then ‘X’ =  13, because sum of factorial of its digits will be  1! + 3! = 1 + 6 = 7, and it is the smallest such integer.

Note:

1. ‘X’ may be large, so return it as a string.
2. A ‘X’, for a positive integer ‘N’, always exists under given constraints.
3. It is guaranteed that the number of digits in ‘X’ will not exceed 10^5.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘T’ lines represent the ‘T’ test cases.

The first and only line of each test case contains the given integer ‘N’.

Output format :

For each test case, print a string that represents the smallest positive integer ‘X’ such that the sum of the factorial of its digit is equal to ‘N’.

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10^9

Time limit: 1 sec

Sample Input 1:

2
1
120

Sample Output 1:

1 
5

Explanation of Sample Input 1:

Test case 1:
The factorial of ‘1’ is  ‘1’  and it is also the smallest positive integer such that the sum of the factorial of its digit is equal to the given ‘N’, i.e 1.

Test case 2:
The factorial of 5 is 120, and it is the smallest positive integer such that the sum of the factorial of its digit is equal to the given ‘N’, i.e 120.

Sample Input 2:

2
40321
32

Sample Output 2:

18
234

Explanation of Sample Input 2:

Test case 1:
The Sum of the factorial of digits of 18 is:
1! + 8! = 1 + 40320 = 40321.
Other positive integers whose sum of the factorial of digits is‘40321’  are  81, 177777777, etc.  But 18 is the smallest of them all. 

Test case 2:
The sum of the factorial of digits of 234 is-:
2! + 3! + 4! = 2 + 6 + 24 = 32
Other positive integers whose sum of the factorial of digits is‘32’ are 324, 423,  22224, etc. But 234 is the smallest of them all.

Console