Algorithms to Sum using Distinct Positive Factorial Numbers

Given a positive integer n, return whether n can be written as the sum of distinct positive factorial numbers.

Example 1
Input
n = 31
Output
true
Explanation
Since 31 = 4! + 3! + 1!

Example 2
Input
n = 4
Output
false
Explanation
Since 4 = 2! + 2! but not distinct.

Example 3
Input
n = 6
Output
true
Example 4
Input
n = 29
Output
false

Depth First Search Algorithm

First of all, we need to pre-calculate the factorials that are less or equal than the given number N. Then, we can perform a DFS (Depth First Search) algorithm to pick up factorials until it can be represented by sum of them or otherwise return false.

bool factorialSum(int n) {
    vector<long long> f;
    long long s = 1;
    for (int i = 1; s <= n; ++ i) {
        s *= i;
        f.push_back(s);
    }
    sort(rbegin(f), rend(f));
    function<bool(int, int)> dfs = [&](int left, int n) {
        if (n == 0) {
            return true;
        }
        for (int i = left; i < f.size(); ++ i) {
            if (n >= f[i]) {
                if (dfs(i + 1, n - f[i])) {
                    return true;
                }
            }
        }
        return false;
    };    
    return dfs(0, n);
}

Greedy Algorithm

Since, for any factorials f(i), it is always greater than sum of f(1) to f(i-1), thus we can use the Greedy Algorithm to deduct the largest factorials if possible until we can’t. Finally we just need to check if the remainder is zero or not.

bool factorialSum(int n) {
    vector<long long> f;
    long long s = 1;
    for (int i = 1; s <= n; ++ i) {
        s *= i;
        f.push_back(s);
    }
    sort(rbegin(f), rend(f));
    for (int i = 0; i < f.size(); ++ i) {
        if (n >= f[i]) {
            n -= f[i];
        }
    }
    return n == 0;
}

Sum of Distinct Positive Factorial Numbers:

• Teaching Kids Programming – Sum of Distinct Positive Factorial Numbers
• Algorithms to Sum using Distinct Positive Factorial Numbers
• Teaching Kids Programming – Sum of Distinct Positive Factorial Numbers via Depth First Search Algorithm

–EOF (The Ultimate Computing & Technology Blog) —