Why is my c++ code unable to scale up input?

Question

Here is my code for a problem in CSES problem set "Distinct Numbers". The problem basically inputs an integer (i) specifying the no. of elements and and an array of length equal i. We basically have to find the distinct no. of elements in that array.

#include <iostream>

using namespace std;

bool check(unsigned long long int val, unsigned long long int arr[], unsigned long long int range) {
    unsigned long long int i;
    bool return_val = true;
    for (i=0; i<range; i++) {
        if (arr[i] == val) {
            return_val = false;
        }
    }
    return return_val;
}

int main()
{
    //cout << "DEBUG-1" << endl;
    unsigned long long int i;
    cin >> i;

    unsigned long long int in_array[i];
    unsigned long long int j;
    for (j=0; j<i; j++) {
        cin >> in_array[j];
    }
    unsigned long long int sort_array[i];
    unsigned long int long sort_array_index = 0;
    for (j=0; j<i; j++) {
        if(check(in_array[j], sort_array, sort_array_index)) {
            sort_array[sort_array_index] = in_array[j];
            sort_array_index++;
         }
    }
    cout << sort_array_index;
}

When the input is not huge and is limited to 2 digit inputs, the code works fine.

The problem I'm facing is that when the input is 200000, my code breaks and shows there is no output as the time limit for compilation exceeds 1 second. Here is my issue: There's a test case on the site in which i=200000, and the array consists of all 1's. The obvious answer is 1 and my output is also 1. But, when i=200000, and all values are distinct the above issue occurs and the input displayed on the test is (empty).

Even when I include the first cout << "DEBUG-1" << endl; line (commented out), it is not seen in the output, whereas it is even before the first input line. It's like the program just rejects the input on seeing it. What I'm not able to understand that I wrote a similar program for an earlier problem and it worked fine on big inputs. Please tell me what is going wrong and include suggestions to write better code as well.

Answer 1

It might be that reading input takes too long. You can make it faster by reading all input at once (std::getline if they are on one line) and then splitting it.

Another problem could be that you are creating large arrays. Instead, use std::unordered_map for counting and create entries only for the numbers you need:

#include <unordered_map>
// ...

std::unordered_map<unsigned long long, unsigned int> sort_array;
for (j=0; j<i;j++) {
    sort_array[in_array[j]]++;
}
cout << sort_array.size();

Or you could read while you are counting, which eliminates the need of in_array:

std::unordered_map<unsigned long long, unsigned int> sort_array;
for (j=0; j<i;j++) {
    int number;
    cin >> number;
    sort_array[number]++;
}
cout << sort_array.size();

Note: This code also counts how many instances of each number there are, which is unnecessary for your problem but should take the same time as the other answer using unordered_set.

Answer 2

Your program is using an N-squared algorithm.

That is, as your sort_array_index value keeps increasing, each subsequent scan of sort_array takes longer and longer. (One minor optimization - break out of the loop as soon you set return_val to false. But that's not going to be a significant savings).

Your entire program can be simplified to use the unordered_set class as a hash table for O(1) insertion and duplicate detection on each of the N elements inserted. Hence, an O(N) algorithm

#include <unordered_set>
#include <iostream>

using namespace std;

int main()
{
    size_t i;
    std::unordered_set<long long> table;

    cin >> i;  // number of elements to read

    // read the elements
    for (size_t j=0; j<i; j++) {
        long long value;
        cin >> value;
        table.insert(value);
    }

    size_t unique_element_count = table.size();
    cout << unique_element_count;

    return 0;
}