Teaching Kids Programming – Sum of Distinct Positive Factorial Numbers


Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Hints:
Can we generate all factorials up to n?
super increasing sequence knapsack

Algorithm to Check Sum of Distinct Positive Factorial Numbers

The sum of all factorials up to f(i) is always smaller than f(i+1):

tex_754aa69fe3baf2d2b3a80407a4234e2d Teaching Kids Programming - Sum of Distinct Positive Factorial Numbers algorithms math python teaching kids programming youtube video which is bigger than
tex_0d81a63a2e548bab03f2867567b1747b Teaching Kids Programming - Sum of Distinct Positive Factorial Numbers algorithms math python teaching kids programming youtube video and tex_0d81a63a2e548bab03f2867567b1747b Teaching Kids Programming - Sum of Distinct Positive Factorial Numbers algorithms math python teaching kids programming youtube video is bigger or equal to tex_eb51bb79f6f2d2331b06d5f3d84d8ad9 Teaching Kids Programming - Sum of Distinct Positive Factorial Numbers algorithms math python teaching kids programming youtube video
And thus: tex_dfba41fbcaf62dad31f4c1a431d6450c Teaching Kids Programming - Sum of Distinct Positive Factorial Numbers algorithms math python teaching kids programming youtube video is larger than tex_eb51bb79f6f2d2331b06d5f3d84d8ad9 Teaching Kids Programming - Sum of Distinct Positive Factorial Numbers algorithms math python teaching kids programming youtube video

We then can greedly subtract the largest factorial number that is less or equal to n until we can’t. If the remainder is zero then we can use the distinct factorial numbers to sum up to n. If we try the smallest factorial number first, we may risk to reduce the sum too early and including a higher sum may not be possible.

We pre-compute the factorials and store them in array which is O(N) space and time. And then starting from the largest number, we try to reduce the sum.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def factorialSum(self, n):
        fact = x = 1
        res = []
        while fact <= n:
            fact *= x
            res.append(fact)
            x += 1
        for i in range(len(res) - 1, -1, -1):
            if n >= res[i]:
                n -= res[i]
        return n == 0
class Solution:
    def factorialSum(self, n):
        fact = x = 1
        res = []
        while fact <= n:
            fact *= x
            res.append(fact)
            x += 1
        for i in range(len(res) - 1, -1, -1):
            if n >= res[i]:
                n -= res[i]
        return n == 0

Given n is a signed 32-bit number, there are 12 distinct factorials within this range i.e. 12!=479001600 which is the largest factorial in 32-bit signed range. Therefore The time complexity is O(12)=O(1). And so is space complexity.

And we can use the Recursive Depth First Search Algorithm to pick or not pick each item: Teaching Kids Programming – Sum of Distinct Positive Factorial Numbers via Depth First Search Algorithm

Sum of Distinct Positive Factorial Numbers:

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
802 words
Last Post: GoLang: Range Sum Query on Immutable Array via Prefix Sum
Next Post: GoLang: Full Permutation Command Line Tool

The Permanent URL is: Teaching Kids Programming – Sum of Distinct Positive Factorial Numbers

Leave a Reply