[Beauty of Programming 2.2] Don't Be Scared by Factorials

The problem asks to count the number of trailing zeros in n!. This is essentially counting how many multiples of 5 are multiplied in during the computation of n!.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int CountZero(int n)
{
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int tmp = i;
        while (0 == i % 5)
        {
            cnt++;
            tmp /= 5;
        }
    }
    return cnt;
}

The problem asks for the position of the lowest bit 1 in the binary representation of N!. We can observe that multiplying by odd numbers doesn’t affect the position of 1. Each time we multiply by 2, the entire value shifts left by 1 bit. Therefore, the result depends on the number of times 2 appears as a factor.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
int CountBinaryOne(int n)
{
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        int tmp = i;
        while (0 == tmp % 2)
        {
            cnt++;
            tmp /= 2;
        }
    }
    return cnt;
}