Total no of unique values in array for larger max value(10^9)

One solution is to create an array of size = (max element in array) and then mark that element as 1 in array if it found otherwise 0. And after that count no of 1 of unique no of elements in array.

But Here’s a problem when I need to mark large integers like 10^9. I can’t create such large array. So,Instead I created a Hash Table and stored my data in it.

Storing value in hashmap and then finding the size of hash map take much time as STL or these hash maps are slow.

Can you guys suggest any other efficient solution of it. I hope you guys always have something new.

You can follow these steps :-

1.)Perform radix sort on the data with runtime O(n lg Z) (where Z is the maximum value in the array).

2.)Once sorted you can make one pass through the array tallying occurrences of each value. Because the array is sorted, once a value changes you know you’ve seen all occurrences of the previous value.

Edit: I am not sure about this for larger value but you can use set() or multiset() and print the size.

Hope it helps :slight_smile:

Sort the array and increment the counter only if the current element and next element are unequal.
Eg. 4 5 6 3 3 5 4

After sorting : 3 3 4 4 5 5 6

               0 1 1 2 2 3 4

Alternatively you can use std::unique from STL library.

You can use a HashMap and do the following while inserting the data in it:-

map<int,int> arr;
//suppose there are n elements in an array 'a'
for(int i=0;i<n;i++){
    if(arr.find(a[i])!=arr.end()){
        distinctElementCount++;
        arr.insert(pair<int,int>(a[i],1));
    }
}
cout<<distinctElementCount;

Ok , you can use Trie data structure , treat each number as a string , and for every ith position , check whether the string is present in a trie or not . If not present then increment the answer and insert that string in to the trie.

int res = 0;

for(int i = 0 ; i < N ; ++i ){

string x;

cin >> x;

if(trie.find( x ) == false ){

 res++;

trie.insert( x );  // during inserting mark the starting and ending postion , 

}

}

O( N * MAXIMUM_DIGITS( Ai ) ) time complexity

Hashmap technique will be slow for such large value.

//