Memory limit exceeded

Question

Please help as I don't understand why I am exceeding the memory limit when I add a new item to the array, is it exceeded due to something else? this is an excerpt from my code:

int min=1000000,max=0;

unsigned char tab1[min+1];

int n=0, input=0, b=0;

std::cin>>n;

for (int i = 0; i < n ; i++) {
std::cin >> input;
if(input < min) { min=input;}
if(input > max) { max=input;}
tab1[input]= '1';
}

 

Answer 1

Can you explain what you want to do?

The first error is that there is no constant for the size of the array.

For example: 

const int tab1Len = 100000

The second thing is that when adding another element to an array, you should use the next elements of that array:

I don't understand why you want to put a element in an input number that someone will give you in the console.

If you want to do this, better think is create something like:

struct nameOfYourStruct {
  char val;
   int pos;
};

if you explain what you mean, maybe I can help you better.

 

If you want for example put '1' to 'input' element of array, first you need to initialize this array:

for(int i = 0; i < lenArray; i++)
   array[i] = 0;

 

Comments

This is the content of the quest:

Input:

In the first line, the program gets the number n. In the next line it gives n data numbers, each of which is in the range <0, 1000000>.

Output:

On the output, list how many unique pairs of numbers (b) can be formed, where a is a divisor of b.

1 ≤ n ≤ 500,000

This table is a kind of "logical array", when i write on input 1 i put '1' at index 1 then go through the multiples of the number to find x pairs

---

if the tab1 is defined on the stack, it can make the problem (if the stack is limited to less than 1MB).

Make this array either a global or static one.

Answer 2

Do not use Variable Length Array (VLA) in your code. It is not part of the standard in C++. Nonetheles some compilers allow using of such statments ( in spite of backward compatibility to C language ), VLA array is still allocated on stack, which despite everything has limited size to fit in one milion element.

Your problem can be solved using std::set and std::vector containers. See following example:

#include <iostream>
#include <iterator>
#include <set>
#include <vector>

using namespace std;

int main()
{
  istream_iterator<int> cit(cin);
  set<int> data( istream_iterator<int>{cit} , istream_iterator<int>{} );

  vector<pair<int,int>> result;
  for( auto it {cbegin(data)} ; it != prev(cend(data)) ; ++it )
  {
      for( auto it_inner {next(it)} ; it_inner != cend(data) ; ++it_inner )
      {
           if( *it_inner % *it == 0 ) result.emplace_back(make_pair(*it,*it_inner));
      }
  }

  for( const auto element : result ) cout << element.first << "," << element.second << endl;
}

https://godbolt.org/z/3hqa4cvPP