UVA - 12955 - Factorial

This article will explain my thought process to solve a problem called Factorial (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Dynamic Programming, Coin Change

Problem Summary

Given:

Factorial sum.

We want to:

Find the minimum amount of factorial that has sum equals to the factorial sum.

Glossary

Dynamic Programming (DP) — A method used to solve complex problems by breaking them into smaller overlapping subproblems and storing their results to avoid recomputation.
Coin Change (CC) — A classic algorithmic problem that involves finding the minimum number of coins needed to make a certain amount of change.

Observation

The factorials can also be expressed as a recurrence relation of factorial(n) = n * factorial(n - 1), which can be computed efficiently using DP top-down or bottom-up approaches.

The factorial sum is a number that is composed from the elements of the factorials. There is no limit on how many times a factorial can be used on the sum. Since the goal is to find the minimum number of such factorials, it is similar to the CC problem where the factorials are the “coins”, the factorial sum is the “amount of change”, and the total factorials are the “total coins”.

After we’ve discovered the minimum total factorials using CC, to further optimize the process, we can use pre-compute strategy to calculate every possible factorials the minimum total factorials ahead of the process.

Algorithm

The factorials can be implemented using DP bottom-up approach, which is done by iteratively multiply i-th number with the previous i-th factorial result. Since 10! is roughly equals to 3 × 10^6, this number has exceed the input constraints of 10^5, so there is no need to compute the factorials any further.

The factorial sum is implemented with CC algorithm, which is done by (1) combining the factorials with the existing factorial sums until there are no new factorial sums, and (2) keeping track of the number of factorials at every iteration.

The time complexity of this solution is O({total factorial sums} * {total factorials} * {maximum quantity}) or O(10^7).

Implementation

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * 12955 - Factorial
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4834
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        while (in.hasNextInt()) {
            final Input input = new Input();
            input.factorialSum = in.nextInt();

            final Output output = process.process(input);
            out.println(output.factorialSumQuantity);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int factorialSum;
}

class Output {
    public int factorialSumQuantity;
}

class Process {
    private final int[] factorialList;
    private final int[] factorialSumList;

    public Process() {
        this.factorialList = getFactorialList(10);
        this.factorialSumList = getFactorialSumList(100_000);
    }

    public Output process(final Input input) {
        final Output output = new Output();
        output.factorialSumQuantity = factorialSumList[input.factorialSum];
        return output;
    }

    private int[] getFactorialList(final int max) {
        final int[] factorials = new int[max + 1];
        factorials[0] = factorials[1] = 1;
        for (int i = 2; i <= max; i++) {
            factorials[i] = i * factorials[i - 1];
        }

        return factorials;
    }

    private int[] getFactorialSumList(final int max) {
        final int[] coinChange = new int[max + 1];
        Arrays.fill(coinChange, Integer.MAX_VALUE);

        for (final int factorial : factorialList) {
            if (factorial > max) continue;

            coinChange[factorial] = 1;
        }

        boolean hasUpdate = true;
        while (hasUpdate) {
            hasUpdate = false;

            for (final int factorial : factorialList) {
                for (int factorialSum = coinChange.length - 1; factorialSum >= 0; factorialSum--) {
                    final int count = coinChange[factorialSum];
                    if (count == Integer.MAX_VALUE) continue;

                    final int newFactorialSum = factorialSum + factorial;
                    final int newCount = count + 1;
                    if (newFactorialSum > max) continue;
                    if (newCount >= coinChange[newFactorialSum]) continue;

                    hasUpdate = true;
                    coinChange[newFactorialSum] = newCount;
                }
            }
        }

        return coinChange;
    }
}