CODEWITHSUNDEEP
c++stlfactorial
dagwood
dagwood

Reputation: 409

factorial for large numbers giving wrong output

I am trying to find the factorial of large numbers

I input t number of test cases

and a number in each case whose factorial I am trying to find

I am storing the digits of the factorial in a vector (dynamic array)

and multiplying it each time with decremented n's value

function display: displays all digits in vector v

#include <iostream>
#include <vector>

using namespace std;

void display(vector<int> v)
{
    for(int x : v)
    {
        cout << x;
    }
    cout << endl;
}


vector <int> factorial(int n)
{
    vector <int>v;
    if(n > 9)
    {
        int n1 = n;
        int r;
        while(n1 != 0)
        {
            r = n1 % 10;
            n /= 10;
            v.insert(v.begin(), r);
        }
    }
    else
    {
        v.push_back(n);
    }
    --n;
    int pdt;
    int carry = 0;
    int digit;

    while(n != 1)
    {
        for(int i = v.size() - 1; i >= 0; --i)
        {
            pdt = v[i] * n + carry;
            carry = pdt / 10;
            digit = pdt % 10;
            v.insert(v.begin() + i, digit);
            // display(v);
        }
        if(carry != 0)
        {
            if(carry > 9)
            {
                int n1 = n;
                int r;
                while(n1 != 0)
                {
                    r = n1 % 10;
                    n /= 10;
                    v.insert(v.begin(), r);
                }

            }
            else
            {
                v.insert(v.begin(), carry);
            }
            
        }
        carry = 0;
        --n;
    }

    return v;  
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >>n;
        vector <int> v;
        v = factorial(n);
        display(v);
    }
}

output for n = 5

1264221101505

Upvotes: 0

Views: 174

Answers (1)

Damien
Damien

Reputation: 4864

There were several issues in the code. The main one is that the current vector is never modified: each time a new digit is found, it is inserted. There was also the issue of having one variable used instead of another one.

Moreover, the code could be greatly simplified with the convention that v[0] corresponds to the LSB and not the MSB.

There was also the possibility to simplify the code by avoiding useless tests, as if (n > 9 ....).

Here is a working code: 

#include <iostream>
#include <vector>

void display (std::vector<int> &v) {
    for (int i = v.size() -1 ; i >= 0; --i) {
        std::cout << v[i];
    }
    std::cout << "\n";
}

std::vector<int> factorial (int n) {
    std::vector<int> v; 
    v.push_back(1);

    while (n != 1) {
        int carry = 0;
        for (int i = 0; i < v.size(); ++i) {
            int pdt = v[i] * n + carry;
            carry = pdt / 10;
            v[i] = pdt % 10;
        }
        while (carry != 0) {
            int r = carry % 10;
            carry /= 10;
            v.push_back(r);
        }
        --n;
    }
    return v;  
}

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        auto v = factorial(n);
        display(v);
    }
}

Upvotes: 1

Related Questions