468,752 Members | 1,263 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,752 developers. It's quick & easy.

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

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

33 posts views Thread by patrick_woflian | last post: by
11 posts views Thread by Martin Jørgensen | last post: by
8 posts views Thread by salman | last post: by
59 posts views Thread by Umesh | last post: by
3 posts views Thread by Sugandh Jain | last post: by
35 posts views Thread by rajash | last post: by
3 posts views Thread by Blue sky | last post: by
1 post views Thread by CARIGAR | last post: by
reply views Thread by zhoujie | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.