Unable to have 100 factorial with C++ on output screen(displaying 0)

Question

Well I am stuck on this problem for quite a while:

Question: You are asked to calculate factorials of some small positive integers.

---

Input:

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100.

---

Output:

For each integer n given at input, display a line with the value of n!

//coded in c++
#include <bits/stdc++.h> //loadind up all the libraries at once.
using namespace std;

int main()
{   int T;
    scanf("%d", &T); 

//I am not doing "cin<<" cause "scanf" is faster than it

    for (int i = 0; i < T; i++)
    {
        int N;
        scanf("%d",&N);
        long long int product = 1;
        while (N >0){
            product = product * N;
            N--;
        }
        printf("%lld\n",product);
    }    
    return 0;
}

I am able to get 10!,20! but unable to get 100! (factorial) so the extreme case doesn't satisfy. Please help me to get a good data type for my variable as 100! a factorial has over than 100 digits. It is displaying 0 when I input 100 on the terminal.

P.S - This problem is from CodeChef website (FCTRL2).

Answer 1

A 64bit integer will overflow with 23!

Therefore you need to do it with digits and a vector.

This is a rather simple task. We can do it like we would do it on a piece of paper. We use a std::vector of digits to hold the number. Because the result will be already too big for an unsigned long long for 23!.

The answer will be exact.

With such an approach the calculation is simple. I do not even know what to explain further.

Please see the code:

#include <iostream>
#include <vector>

int main()
{
    std::cout << "Calculate n!   Enter n (max 10000): ";
    if (unsigned int input{}; (std::cin >> input) && (input <= 10000)) {

        // Here we store the resulting number as single digits
        std::vector<unsigned int> result(3000, 0);  // Magic number. Is big enough for 100000!
        result.back() = 1;                          // Start calculation with 1 (from right to left)

        // Multiply up to the given input value
        for (unsigned int count = 2; count <= input; count++)
        {
            unsigned int sum{}, remainder{};
            unsigned int i = result.size() - 1;     // Calculate from right to left
            while (i > 0)
            {
                // Simple multiplication like on a piece of paper
                sum = result[i] * count + remainder;
                result[i--] = sum % 10;
                remainder = sum / 10;
            }
        }
        // Show output. Supporess leading zeroes
        bool showZeros{ false };
        for (const unsigned int i : result) {
            if ((i != 0) || showZeros) {
                std::cout << i;
                showZeros = true;
            }
        }
    }
    else std::cerr << "\nError: Wrong input.";
}

Using a bigint library will be much faster.

---

Developed and tested with Microsoft Visual Studio Community 2019, Version 16.8.2.

Additionally compiled and tested with clang11.0 and gcc10.2

Language: C++17