Suppose I need to mark the presence of few numbers,so I would set - array[i] as 1 and all others as 0.
This would indicate That number i is present.
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.
This is the only solution I could think of.Can anybody suggest me a better approach?
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
int mark[MAX/32];
where MAX is maximum integer we need to mark. what we are going to do is, mark[0] = 0 initially, we are going to set 32 numbers in one index! suppose we get 18, what we will do is
mark[0] = (mark[0] | (1<<18)
it will make mark[0] 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 
Wow!That was clever!Using BIT arrangement and marking a bit to indicate the presence of an integer instead of alloting an entire index to a number.
Thanks for sharing!
Your are welcome mark it as answered if it answer’s your question