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! = 6Example 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 | 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 |
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.
1 2 3 4 5 6 7 8 9 10 11 12 | 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 |
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) —
GD Star Rating
loading...
306 wordsloading...
Last Post: Caesar Cipher Algorithm in C++
Next Post: Teaching Kids Programming - Compute the Sum of the Digits using Three Methods