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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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);
}

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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;
}

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) —