find count of specific digits in a large factorial

user_14782128 0
Viewed 147

I need to calculate count of a specific digit (between 0 & 9) in a large factorial of number

#include <stdio.h>
int main()
{
    unsigned long long int x;
    int n , count = 0;
    scanf("%llu %d", &x , &n);
    int i = x - 1;
    while(i > 1)
    {
        x *= i;
        i--;
    }
    while (x>0)
    {
        if(x%10 == n) count++;
        x /= 10;
    }
    printf("%d",count);
    return 0;
}

This works well for small numbers
input : 7 0
output : 2
description : 7! = 5040 which has two zeros
But takes a long time for large numbers
input : 50 2
output : overflow and time limit!

Is there any idea to optimize this program in terms of time? for example a mathmatic way for calculate number of digits without calculate factorial

factorial count optimization c
1 Answers

Finally i found my answer, which could be helpful for others.

The Idea is using big numbers multiplication:

#include<stdio.h>

int main()
{
    int n , p;
    scanf("%d %d" , &n , &p);
    int digits[1000] = {1};
    for(int i = 2 ; i <= n ; i++)
    {
        for(int k = 0 ; k < 1000 ; k++) digits[k] *= i;
        for(int k = 0 ; k < 1000 ; k++) if(digits[k] > 9)
            {
                digits[k+1] += digits[k]/10;
                digits[k] %= 10;
            }
    }
    int a , count = 0;
    for(a = 999 ; !digits[a] ; a--);
    a++;
    for (int j = 0;j<a;j++) if(digits[j] == p) count++;
    printf("%d" , count);
}
user_147821280
Related