Marking large integers

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?

1 Like

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 :slight_smile:

6 Likes

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 :slight_smile: mark it as answered if it answer’s your question :slight_smile: