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 an inbuilt stack.

Method 1

To calculate factorial without a stack, we use a variable and initialize it to 1. We then multiply the variable by all numbers from 2 to N. Instead of using a 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;
	}
}

// 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)

We can reduce the space complexity of the 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;
	}
}

// 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;

}
#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) {
		int temp = stk.top();
		stk.pop();
		stk.push(temp * i);
	}

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

	return 0;

}

Output

Enter a number: 6
Factorial: 720

Read

Leave a Comment

Your email address will not be published. Required fields are marked *