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.

C/C++
C++

#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;
	}
}

// return top element of the stack
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.

C/C++

#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;
	}
}

// return top element of the stack
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

Read

Leave a Comment Cancel Reply