# C/C++ Program to find factorial using stack

Write a program to find factorial using stack in c/c++.

Example,

```Input: 5
Output: 120```

For this tutorial, we will implement our own stack. If you are using C++ then you may use the inbuilt stack.

Method 1

To calculate the factorial of a number N without a stack, we use a temporary variable and initialize it to 1. We then multiply the temporary variable by all numbers from 2 to N. Instead of using a temporary variable, we will use the stack to store the partial product of numbers.

```#include<stdio.h>

int stk[100]; // stack
int size = 100;	// size of stack
int ptr = -1; // store the index of top element of the stack

// push x to stack
void push(int x){
if(ptr==size-1){
printf("OverFlow \n");
}
else{
++ptr;
stk[ptr] = x;
}
}

int top(){
if(ptr==-1){
printf("UnderFlow \n");
return -1;
}
else{
return stk[ptr];
}
}

// remove top element from the stack
void pop(){

if(ptr==-1){
printf("UnderFlow \n");
}
else{
--ptr;
}
}

// check if stack is empty or not
int isempty(){
if(ptr==-1)
return 1;
else
return 0;
}

int main() {

int i, n;

printf("Enter a number: ");
scanf("%d", &n);

push(1);
for(i=2;i<=n;++i){
push(top() * i);
}

printf("Factorial: %d", top());

return 0;

}
﻿```
```#include <iostream>
#include <stack>
using namespace std;

int main() {

int n;
cout << "Enter a number: ";
cin >> n;

stack<int> stk;
stk.push(1);
for (int i = 2; i <= n; ++i) {
stk.push(stk.top() * i);
}

cout << "Factorial: " << stk.top() << endl;

return 0;

}```

Output

``````Enter a number: 5
Factorial: 120
``````

Time Complexity: O(N)
Space Complexity: O(N)

Method 2

We can reduce the space complexity of the above program to O(1). We are only using the top value of the stack. We can pop the other elements. See the code given below.

```#include<stdio.h>

int stk[100]; // stack
int size = 100;	// size of stack
int ptr = -1; // store the index of top element of the stack

// push x to stack
void push(int x) {
if (ptr == size - 1) {
printf("OverFlow \n");
}
else {
++ptr;
stk[ptr] = x;
}
}

int top() {
if (ptr == -1) {
printf("UnderFlow \n");
return -1;
}
else {
return stk[ptr];
}
}

// remove top element from the stack
void pop() {

if (ptr == -1) {
printf("UnderFlow \n");
}
else {
--ptr;
}
}

// check if stack is empty or not
int isempty() {
if (ptr == -1)
return 1;
else
return 0;
}

int main() {

int i, n, temp;

printf("Enter a number: ");
scanf("%d", &n);

push(1);
for (i = 2; i <= n; ++i) {
temp = top();
pop();
push(temp * i);
}

printf("Factorial: %d", top());

return 0;

}
﻿```

Output

``````Enter a number: 6
Factorial: 720``````