Last Updated: 12 Dec, 2020
Fact Digit Sum
Easy
Asked in company
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.
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
Approaches
- Make an array ‘fact’ of size 10.
- Precompute factorials from 0 to 9 and store them in an array ‘fact’ such that fact[i] represents factorial of ‘i’.
- Initialize an integer variable X:= ‘1’.
- Run a while loop and in each iteration do the following -:
- Initialize an integer variable ‘factDigitSum’ = 0.
- Iterate over digits of ‘X’ and add factorial of a current digit in ‘factDigitSum’.
- If ‘factDigitSum’ is equal to ‘N’ then break the loop.
- If ‘factDigitSum’ is not equal to ‘N’ then increment ‘X’ by 1.
- Convert the integer ‘X’ obtained into the string and return this string.
Note: This approach will give ‘Time Limit Exceeded’ if ‘X’ is a large integer.
Approach:
Notice that for any digit ‘d’ > 1, d! = d*((d-1)!). This implies that if you do not select digit ‘d’,then you need digit ‘d-1’, exactly ‘d’ times to have a digit factorial sum equal to single-digit ‘d’. It suggests giving priority to larger digits first, in order to find the smallest positive integer ‘X’.
For example, if ‘N’ = 40321, ‘X’ will be ‘18’ as 1! + 8! = 40321. f instead of digit ‘8’ in ‘X’, we select a smaller digit ‘7’ to be included as a digit in integer ‘X’, then the value of ‘X’ such that it includes 7 as the maximum digit will be 177777777, which is very large in comparison to 18, so we drop 7 and choose 8 instead.
So, our approach can be performed in the following steps -:
- Make an array ‘fact’ of size 10.
- Precompute factorials from 0 to 9 and store them in an array ‘fact’ such that fact[i] represents factorial of ‘i’.
- Make a stack ‘digits’ in which we will store all digits of answer ‘X’.
- Run a loop where ‘i’ ranges from 9 to 1 and do following -:
- Initialize an integer ‘digitFreq’ and assign ‘digitFreq’ := N/fact[i].
- ‘digitFreq’ now has the frequency of digit ‘i’ in answer ‘X’.
- Run a loop to push digit ‘i’ in stack ‘digits’, exactly ‘digitFreq’ times.
- Update N:= N % fact[i], so ‘N’ will be equal to the digit factorial sum required now.
- Stack ‘digits’ will consist of all the digits that should present in ‘X’ in non-decreasing order from top to bottom.
- Iterate the stack ‘digits' from top to bottom and append all digits in a string to form the smallest positive integer having digit factorial sum ‘N’ and then return this string.