While
Stalker's advice about line 13 is technically correct, the GCC does allow VLAs like this. Nevertheless, I agree with the instruction. For a general purpose container, create an array and track its size:
1 2 3
|
constexpr int MAX_SIZE = 40;
int numbers[ MAX_SIZE ];
int used = 0;
| |
1 2
|
// add '4' to the end of the array
numbers[ used++ ] = 4;
| |
1 2 3
|
// print the array
for (int n = 0; n < used; n++)
cout << numbers[ n ] << "\n";
| |
etc.
Now, on to your actual issue: O(n²) complexity. This happens because you have to loop over the array for every number, just to determine whether or not it is present. You can reduce complexity by improving the "is it present" test.
The first idea that comes to mind is to
sort your data. This can easily be done in less than O(n²) time. Once done, you only need a linear O(n) pass over it to get the missing numbers. Your time is now the same as whatever it took to sort your array [O(n log n) for
std::sort() → O(n log n)+O(n) → O(n log n)].
If your range of values is sufficiently small, however, you can reduce it to O(3n) → O(n) time by using the values as
indices into the array.
O(n): create/fill the array with zeros
O(n): read the numbers, adding 1 to
array[n] for every
n you read.
O(n): scan through the array, printing out all the
ns that have a count of 0.
Hope this helps.