Try using bits to mark integers. It will decrease your memory by size of type of array. As in lets say we have an array of integer type
where MAX is maximum integer we need to mark. what we are going to do is, mark = 0 initially, we are going to set 32 numbers in one index! suppose we get 18, what we will do is
mark = (mark | (1<<18)
it will make mark sumthing like 00000000000000100000000000000000 , marking the 18th bit, so we can mark numbers like this and to check. a simple way can me
mark[(n)/32] = (mark[n/32] | (1<<(n%32))
this should work!.
now how to check hash table, approach is similar, there should be one in that place…
if(mark[n/32]&(1<<(n%32)) then yes else no
using this your memory reduced by 32, you can reduce it by 64 also using long long!
Other method of saving long numbers as hash is using stl map. Just declare map<int,int> mp and mark it as mp[n] = 1;
check if marked as
if(mp[n]) then true else false.
complexity will be log(n) for both cases
You can also read more about unordered_map with O(1) amortized complexity. I didn’t used it till now, but you can have a read