Why vector in C++ doesn't resize automatically

I've a very long factorial program which needs to find factorial up to 100. It works well up to 33 factorial but not from 34. Can someone help in identifying the problem.

#include <iostream>
#include <vector>
#include <utility>


using namespace std;

void bigFactorials(int n)
{
    vector<int> v;//If I specify the size as v(1000) it works fine but I don't 

    //want to specify the size beforehand.
    v.push_back(1);

    // Complete this function
    for(int i=2;i<=n;i++) {
        int carry = 0, mul=0;
        for(auto j=v.rbegin();j!=v.rend();j++) {
            mul=i**j + carry;
            carry=mul/10;
            *j=mul%10;
        }

        if(carry)
            v.insert(v.begin(),carry);    
    }

    for(int i:v)
        cout<<i;
}

int main()
{
    int n;

    cin >> n;
    if( n>0 && n<101 )
        bigFactorials(n);

    return 0;
}

3 answers

  • answered 2018-02-15 07:41 Stephen Docy

    You are definitely overflowing, when I print out the carry values that are added to the vector:

    1
    5
    4
    3
    3
    3
    4
    6
    8
    13
    20
    35
    64
    121
    243
    510
    1124
    2585
    6204
    15511
    40329
    108888
    304888
    884176
    2652528
    8222838
    26313083
    86833176
    -134263930
    -134263930-639604140847618609643520000000
    

    I switched to long long for the vector and for carry and mul and was able to get the correct answer for 34!, but 99! still overflows. Seems you need to further reduce the numbers you are adding to the vector.

  • answered 2018-02-15 07:47 rafix07

    Problem is when carry > 10, then you insert one integer value without splitting it into chars, it should be implemented as follows

    if(carry)
    {
        if (carry >= 10)
        {
            while (carry > 0)
            {
                v.insert(v.begin(),carry % 10); // put each char from carry into v
                carry = carry / 10;
            }
        }
        else
            v.insert (v.begin(),carry);
    }
    

    with this you can even keep v as vector<char> and for 50! we have 30414093201713378043612608166064768844377641568960512000000000000.

  • answered 2018-02-15 07:58 Mihayl A. A

    You need to split your carry in decimal digits and insert in-front of your BigInt.

    while (carry)
    {
        v.insert(v.begin(), carry % 10);
        carry /= 10;
    }
    

    Here the whole function:

    void bigFactorials(int n) {
        vector<int> v;//If I specify the size as v(1000) it works fine but I don't 
        //want to specify the size beforehand.
        v.push_back(1);
    
        // Complete this function
        for (int i = 2; i <= n; i++)
        {
            int carry = 0, mul = 0;
            for (auto j = v.rbegin(); j != v.rend(); j++)
            {
                mul = i * *j + carry;
                carry = mul / 10;
                *j = mul % 10;
            }
    
            while (carry)
            {
                v.insert(v.begin(), carry % 10);
                carry /= 10;
            }
        }
    
        for (int i : v)
            cout << i;
    }
    

    Live Demo