Interesting case of algorithm optimization

Here is a task: You need to write a function that takes 2 integers and calculates the factorial of the first number and returns how many zeroes there will be at the end of that factorial at the radix represented by the second number.

For example, for an input (4, 12), the function will return 1, because 4! will be 24 and 24 at radix 12 will be 20.

Acceptable range for a number is from 1 to 1,000,000 and for a radix range is from 1 to 256.

Simplest way to do this task is to calculate factorial and count how many times we can divide factorial by radix without reminder. Obviously that factorial from 1,000,000 is a really big number. Around 10 in power of 5565709. But it is still possible to calculate it by using a library that can handle numbers of arbitrary length. For example, BigInteger class in C#. On my computer it took around 35 minutes to complete. Here is code:

public static int Zeroes1(int number, int radix)
{
    BigInteger factorial = number;
    for (int i = number - 1; i > 1; i--)
    {
        factorial *= i;
    }

    int answer = 0;
    while (factorial % radix == 0)
    {
        factorial /= radix;
        answer++;
    }
    return answer;
}

But 35 minutes is quite a lot of time and there should be some way to optimize it. One of the ideas was to try to divide the factorial by radix after each multiplication. The reason behind was to reduce factorial and speed up multiplication on next steps. But the final time increased by about 2 times because now on each step there is multiplication and reminder. Here is code:

public static int Zeroes2(int number, int radix)
{
    var answer = 0;
    BigInteger factorial = number;
    for (int i = number - 1; i > 1; i--)
    {
        factorial *= i;

        while (factorial % radix == 0)
        {
            factorial /= radix;
            answer++;
        }
    }
    return answer;
}

Next idea was to keep only the last digit of the factorial. Here is that version:

public static int Zeroes3(int number, int radix)
{
    var answer = 0;
    BigInteger factorial = number;
    for (int i = number - 1; i > 1; i--)
    {
        factorial *= i;

        while (factorial % radix == 0)
        {
            factorial /= radix;
            answer++;
        }
        factorial %= radix;
    }
    return answer;
}

But this version is just wrong because the multiplication step can produce a few zeroes at the end instead of one. For example, if the factorial at the current step is 125 and the next number to multiply by is 8, then the factorial will be 1000. But if we reduce 125 to just 5 then the factorial will be just 20 instead of 1000 and 2 zeroes will be lost.

Next step of optimization is quite smart. I found it here. As you know from math, any integer number can be represented as multiplication of prime numbers. And factorial is multiplication of such numbers. Imagine we would like to calculate 5! Instead of calculating 2 * 3 * 4 * 5 * 6, we will calculate prime numbers of each of these numbers and calculate how many times they are in our number.

For example, for 6! We will have following sequence 2 * 3 * 2 * 2 * 5 * 2 * 3 which is 2 ^ 4 * 3 ^ 2 * 5. Symbol ^ means power. Then we do the same with radix. For example, for radix 12 we will have 2 ^ 2 * 3.

Now let’s see what happened when we will divide them:

2 ^ 4 * 3 ^ 2 * 5       
----------------- = 2 ^ 2 * 3 * 5
   2 ^ 2 * 3

As you know from math, during division, we just subtracted powers. 4 – 2 = 2 and 2 – 1 = 1. And to find out how many times we can do it, we must divide them and take the smallest number. 4/2 = 2 and 2/1 = 2. So, answer that 6! at radix 12 will have 2 zeros at the end. Here is code:

private static void MakePrime(int number, Dictionary<int, int> result)
{
    for (var i = 2; i <= number; i++)
    {
        var quantity = 0;
        while (number % i == 0)
        {
            quantity++;
            number /= i;
        }
        if (quantity > 0)
        {
            if (result.ContainsKey(i))
            {
                result[i] = result[i] + quantity;
            }
            else
            {
                result.Add(i, quantity);
            }
        }
    }
}

public static int Zeroes4(int number, int radix)
{
    Dictionary<int, int> basePrime = new Dictionary<int, int>();
    MakePrime(radix, basePrime);

    Dictionary<int, int> numberPrime = new Dictionary<int, int>();
    for (var i = number; i > 1; i--)
    {
        MakePrime(i, numberPrime);
    }

    int min = int.MaxValue;
    foreach (var pair in basePrime)
    {
        var prime = pair.Key;
        if (!numberPrime.ContainsKey(prime))
        {
            return 0;
        }

        var result = numberPrime[prime] / basePrime[prime];
        if(result < min)
        {
            min = result;
        }
    }
    return min;
}

Code explanation

MakePrime will add prime numbers and their powers to the dictionary. Key is a prime number and value is a power of that prime number. For example, for 2 * 3 * 4 * 5 * 6 you will get the following pairs {2, 4}, {3, 2}, {5, 1}. At the end there will be prime numbers for radix and for factorial. After that, we try to find how many times we can divide power of prime numbers of factorial by power prime numbers from radix and then pickup smallest of them.

Beauty of the new approach is that we don’t need a BigInteger class to do all these calculations and as a result they are much faster. According to the Internet there are 78,498 prime numbers less than 1,000,000, so the dictionary size will be quite manageable.

Unfortunately the new version takes almost 4 minutes to calculate prime numbers for 1,000,000!. Is there anything we can do better? Perhaps we can optimize finding prime numbers. As you see MakePrime goes over all numbers from 2 to number. Obviously, we don’t need to check even numbers except 2, so we need to check 2, 3, 5, 7 etc. It will speed up MakePrime by about 2 times. Here is updated version of MakePrime:

private static void AddPrime(ref int number, Dictionary<int, int> result, int i)
{
    var quantity = 0;
    while (number % i == 0)
    {
        quantity++;
        number /= i;
    }
    if (quantity == 0)
    {
        return;
    }

    if (result.ContainsKey(i))
    {
        result[i] = result[i] + quantity;
    }
    else
    {
        result.Add(i, quantity);
    }
}

private static void MakePrime(int number, Dictionary<int, int> result)
{
    AddPrime(ref number, result, 2);
    for (var i = 3; i <= number; i += 2)
    {
        AddPrime(ref number, result, i);
    }
}

It took about 2 minutes to complete.

Another optimization would be to use an array with 1 million items instead of a dictionary. This is possible because we know that the max number possible is 1,000,000 and an array will be only 4Mb in size. But there are pretty much no improvement with this approach

But all of these will be small optimizations. Is there anything better? And here is an idea that pushed me to write this article. We don’t need to find all prime numbers of the factorial. For example, as you can see from the example above, we found that 6! has prime number 5, but radix does not have number 5 in the list of its prime numbers. Our algorithm never checks number 5 but spends time calculating it. And a new idea, instead of building a list of all primes and their powers from factorial, we need to find out powers of prime numbers that are present in radix and ignore all other numbers.

For example, when we are building a list of prime numbers for number 1,000,000, there could be up to 1,000,000 divisions. Largest prime number less than 1,000,000 is 999,961. And for that prime number there will be quite a lot of divisions because it is prime. But there are only 54 prime numbers between 1 and 256. Here is new version:

private static Dictionary<int, int> MakePrime(int number)
{
    Dictionary<int, int> result = new Dictionary<int, int>();
    for (var i = 2; i <= number; i++)
    {
        var quantity = 0;
        while (number % i == 0)
        {
            quantity++;
            number /= i;
        }
        if (quantity > 0)
        {
            result.Add(i, quantity);
        }
    }

    return result;
}

private static void MakePrimeEx(int number, Dictionary<int, int> radixPrimes, Dictionary<int, int> result)
{
    foreach (var pair in radixPrimes)
    {
        var quantity = 0;
        while (number % pair.Key == 0)
        {
            quantity++;
            number /= pair.Key;
        }
        if (quantity > 0)
        {
            if (result.ContainsKey(pair.Key))
            {
                result[pair.Key] = result[pair.Key] + quantity;
            }
            else
            {
                result.Add(pair.Key, quantity);
            }
        }
    }
}

public static int Zeroes5(int number, int radix)
{
    Dictionary<int, int> radixPrimes = MakePrime(radix);

    Dictionary<int, int> numberPrimes = new Dictionary<int, int>();
    for (var i = number; i >= 2; i--)
    {
        MakePrimeEx(i, radixPrimes, numberPrimes);
    }

    int min = int.MaxValue;
    foreach (var pair in radixPrimes)
    {
        var oName = pair.Key; // Compare two objects with prime factors 
        if (!numberPrimes.ContainsKey(oName))
        {
            return 0;
        }
        var result = numberPrimes[oName] / radixPrimes[oName];
        if (result < min)
        {
            min = result;
        }
    }
    return min;
}

This version finishes in around 0.08 seconds, and it is a huge improvement. Moreover, this version can work with bigger numbers. For example we put 2,000,000 for Zeroes5 function, it will increase from 0.08 to 0.117. But Zeroes4 (with optimization) will increase from 2 minutes to 7.5 minutes. Even 100,000,000 can be handled by Zeroes5 and it will take only 4.5 seconds whiles Zeroes4 will hours or perhaps even days to finish.

In this post I showed how critical thinking and deep analysis can drastically reduce algorithm complexity and reduce time required from 40 minutes to 0.1 seconds. I hope it helps someone.