**What is Factorial****Factorial Formula****10 factorial****factorial of 5****factorial of 0****Factorial program in python**

a. Factorial Using Iteration

b. Factorial using Recursion**Count Trailing Zeroes in Factorial**

Problem Statement : We intend on covering the basics of factorial and computing factorial of a number using python.

**What is Factorial?**

In simple words, if you want to find a factorial of an positive integer, keep multiplying it with all the positive integers less then that number. The final result that you get is the Factorial of that number. So if you want to find the factorial of 7, multiply 7 with all positive integers less than 7. Those numbers would be 6,5,4,3,2,1. Multiply all these numbers by 7 and the final result is the factorial of 7.

**Formula of Factorial **

Factorial of a number is denoted by n!, is the product of all positive integers less than or equal to n:

n! = n**(n-1)**(n-2)**…..*3**2**1

## 10 Factorial

So what is 10! ? Multiply 10 with all the positive integers which are less than 10.

10! =10**9**8**7**6**5**4**3**2*1=3628800

## Factorial of 5

To find 5!, again do the same process. Multiply 5 with all the positive integers less than 5. Those numbers would be 4,3,2,1

5!=5**4**3**2**1=120

## Factorial of 0

Since 0 is not a positive integer, as per convention, factorial of 0 is defined to be itself.

0!=1

Computing this is an interesting problem. Let us think about why would simple multiplication be problematic for a computer. The answer to this lies in how the solution is implemented.

1! = 1

2! = 2

5! = 120

10! = 3628800

20! = 2432902008176640000

30! = 9.332621544394418e+157

The exponential rise in the values shows us that factorial is an exponential function, and time taken to compute it would take exponential time.

**Factorial Program in Python**

There are two ways of implementing the program to calculate factorial.

a. Iterative approach

b. Recursive approach

Let us consider both the approaches

**Factorial of a number using Iteration in Python**

```
def iter_factorial(n):
factorial=1
while(n>1):
factorial=factorial*n
n=n-1
return factorial
num=int(input("Enter the number: "))
print("factorial of ",num," (iterative): ",end="")
print(iter_factorial(num))
```

Input – Enter the number : 5

Output – Factorial of 5 (iterative) : 120

Consider the iterative program. It takes a lot of time for the while loop to execute. The above program takes a lot of time, let’s say infinite. The very purpose of calculating factorial is to get the result in time. Hence this approach does not work for very large numbers.

**Factorial using Recursion in Python**

```
def recur_factorial(n):
"""Function to return the factorial
of a number using recursion"""
if n == 1:
return n
else:
return n*recur_factorial(n-1)
num=int(input("Enter the number: "))
print("factorial of ",num," (recursive): ",end="")
print(recur_factorial(num))
```

Input – Input – Enter the number : 4

Output – Factorial of 5 (recursive) : 24

On a 16GB RAM computer, the above program could compute factorial values upto 2956. Beyond that it exceeds the memory and thus fails. The time taken is really less when compared to iterative approach. But this comes at the cost of the space occupied.

What is the solution to the above problem?

The problem of computing factorial has a highly repetitive structure.

To compute factorial(4), we compute f(3) once, f(2) twice, and f(1) thrice. As the number increases the repetitions increase. Hence, the solution would be to compute the value once and store it in an array from where it can be accessed the next time the value is required. Therefore, we use dynamic programming in such cases. The conditions for implementing dynamic programming are

- Overlapping sub-problems
- optimal substructure

Consider the modification to the above code as follows:

```
def DPfact(N):
arr={}
if N in arr:
return arr[N]
elif N == 0 or N == 1:
return 1
arr[N] = 1
else:
factorial = N*DPfact(N - 1)
arr[N] = factorial
return factorial
num=int(input("Enter the number: "))
print("factorial of ",num," (dynamic): ",end="")
print(DPfact(num))
```

Input – Enter the number : 6

Output – factorial of 6 (dynamic) : 720

Dynamic programming solution is highly efficient in terms of both time and space complexities.

**Count Trailing Zeroes in Factorial using Python**

Problem Statement : Count the number of zeroes in the factorial of a number using Python

```
num=int(input("Enter the number: "))
# Initialize result
count = 0
# Keep dividing n by
# powers of 5 and
# update Count
temp = 5
while (num / temp>= 1):
count += int(num / temp)
temp *= 5
# Driver program
print("Number of trailing zeros", count)
```

Output

Enter the Number : 5

Number of trailing zeros 1

Learn how to find if a string is a Palindrome

Learn how to print the Fibonacci Series in Python

1