Teaching Kids Programming – Two Algorithms to Compute Inverse Factorials

Teaching Kids Programming: Videos on Data Structures and Algorithms

The factorial of a number n is defined as n! = n * (n – 1) * (n – 2) * … * 1. Given a positive integer a, return n such that n! = a. If there is no integer n that is a factorial, then return -1.

Constraints
n < 2 ** 31
Example 1
Input
a = 6
Output
3
Explanation
3! = 6

Example 2
Input
a = 10
Output
-1
Explanation
10 is not any integer factorial.

Inverse Factorial by Dividing

Try dividing N by 2, 3, 4… until we can’t or the dividend is 1.

class Solution:
    def solve(self, a):
        if a == 1: 
            return 1
        if a <= 0:
            return -1
        i = 2
        while a > 1:
            if a % i != 0:
                return -1
            a /= i
            i += 1
        return i - 1

Inverse Factorial by Multipication

Try multiply the product by 2, 3, 4, until the number is bigger or equal to N. When it is bigger, the given number is not a factorial number, otherwise it is.

class Solution:
    def solve(self, a):
        if a == 1: 
            return 1
        if a <= 0:
            return -1
        s = 1
        i = 2
        while s < a:
            s *= i
            i += 1
        return i - 1 if s == a else -1

–EOF (The Ultimate Computing & Technology Blog) —