Find unique numbers in array

Question

Well, I have to find how many different numbers are in an array.

For example if array is: 1 9 4 5 8 3 1 3 5

The output should be 6, because 1,9,4,5,8,3 are unique and 1,3,5 are repeating (not unique).

So, here is my code so far..... not working properly thought.

#include <iostream>

using namespace std;

int main() {
    int r = 0, a[50], n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < j; k++) {
            if (a[k] != a[j]) r++;
        }
    }
    cout << r << endl;
    return 0;
}

Answer 1

Let me join the party ;)

You could also use a hash-table:

#include <unordered_set>
#include <iostream>

int main() {

    int a[] = { 1, 9, 4, 5, 8, 3, 1, 3, 5 };
    const size_t len = sizeof(a) / sizeof(a[0]);

    std::unordered_set<int> s(a, a + len);

    std::cout << s.size() << std::endl;
    return EXIT_SUCCESS;

}

Not that it matters here, but this will likely have the best performance for large arrays.

---

If the difference between smallest and greatest element is reasonably small, then you could do something even faster:

• Create a vector<bool> that spans the range between min and max element (if you knew the array elements at compile-time, I'd suggest the std::bitset instead, but then you could just compute everything in the compile-time using template meta-programming anyway).
• For each element of the input array, set the corresponding flag in vector<bool>.
• Once you are done, simply count the number of trues in the vector<bool>.

Answer 2

A std::set contains only unique elements already.

#include <set>

int main()
{
    int a[] = { 1, 9, 4, 5, 8, 3, 1, 3, 5 };

    std::set<int> sa(a, a + 9);
    std::cout << sa.size() << std::endl;
}