468,752 Members | 1,263 Online

# digit frequencies in factorial of a number

Can anyone suggest a better solution to finding the digit frequencies in factorial of a number, like

3! = 6
(0) 0 (1) 0 (2) 0 (3) 0 (4) 0
(5) 0 (6) 1 (7) 0 (8) 0 (9) 0

8! = 40320
(0) 2 (1) 0 (2) 1 (3) 1 (4) 1
(5) 0 (6) 0 (7) 0 (8) 0 (9) 0

An obvious way of doing it is to find the factorial and then keep on dividing the number by 10 to get the digits and increment corresponding counters.

Something like:

Expand|Select|Wrap|Line Numbers
1. while(factorial)
2. {
3.     Counters[factorial%10]++;
4.     factorial /= 10;
5. }
Please suggest some solution that is optimized for speed and time.
Jan 8 '07 #1
3 2360
Ganon11
3,652 Expert 2GB
The simplest way I can think of is the way you are doing it - a linear traversal of the number, incrementing the counter, which is O(n) time (decent). I can't think of another way, since there's no way of telling how many of each digit there will be before you calculate the number.
Jan 8 '07 #2
The simplest way I can think of is the way you are doing it - a linear traversal of the number, incrementing the counter, which is O(n) time (decent). I can't think of another way, since there's no way of telling how many of each digit there will be before you calculate the number.
OK. Lets see if someone else can suggest a solution.
Jan 8 '07 #3
What I would suggest is
1) Calculate the factorial of the number
2) Convert the factorial to a character string
3) Write a function to count the occurrence of each character (digit)
Jan 9 '07 #4