C96
C96

Reputation: 529

I am getting the following error: terminate called after throwing an instance of 'std::bad_alloc'

Ok so I have a string s that I repeat n times. For example I have "aba" and n = 10 and I want to find the number of a's. So in this case (abaabaabaa) we have 7 a's. I wrote the following code that passes some of the test cases but when n is big I am getting the error: terminate called after throwing an instance of 'std::bad_alloc. Is there a way to fix it? Thanks.

long repeatedString(string s, long n) {

    long i = 0, j = 0, cnt = 0;
    long sz = s.size();
    vector<char> ar;

    while (i < n)
    {
        ar.push_back(s[j]);
        j++;

        if (j >= sz)
        {
            j = 0;
        }

        i++;
    }

    i = 0;
    while (i < n)
    {
        if (ar[i] == 'a')
        {
            cnt++;
        }
        i++;
    }

    return cnt;

}

Upvotes: 0

Views: 1710

Answers (1)

ChrisMM
ChrisMM

Reputation: 10105

Basically, the cause is that you are running out of memory. When you do push_back, the vector may be reallocating which would require capacity + capacity * 2 (multiplier may vary) amount of space in a contiguous allocation. If you reserve ahead of time, this would fix that problem, but you would still need n contiguous bytes of memory.

A better solution is to just read the string and do some multiplication, like so:

size_t repeatedString( const std::string &s, size_t n ) {
    size_t sz = s.size();
    size_t cnt = 0;

    for ( const char &c : s ) {
        if ( c == 'a' ) {
            ++cnt;
        }
    }

    size_t mult = n / sz;
    cnt *= mult;
    size_t rem = n % sz;

    for ( size_t idx = 0; idx < rem; ++idx ) {
        if ( s[idx] == 'a' ) {
            ++cnt;
        }
    }

    return cnt;
}

This makes it so that you don't need to allocate an additional n bytes, so the memory is reduced.

Upvotes: 3

Related Questions