@arpit728, this is similar to my code in c++. Here is a link to the solution. CodeChef: Practical coding for everyone (for optimised code refer to CodeChef: Practical coding for everyone).
For the details of the indexing of array, let us first consider the genral discussion of marking large integers into array.
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. Here we use know that int is 32 bits longs. So we use each bits of every number to store a value (here 1 means it is present and 0 means it is absent). This means mark[0] will represent 0 to 31 values, mark[2] will represent 64 to 95 values and and so… i.e. mark[i] will represent 32*(i-1) to (32*i)-1 vales.
So for given number n, he first do integer divide (n/32) to get which index of array should taken and to get which bit to check in that index, we take (n%32) which is clear from the above values which are given for nth index which is 32*(n-1) to (32*n)-1.
Suppose we get 18, what we will do is
mark[0] = (mark[0] | (1<<18)
it will make mark[0] something like 00000000000000100000000000000000, marking the 18th bit, so we can mark numbers like this. This actually means mark[0] is given the value 2^18 = 262144. As you see my first implementation, to find the sum I have checked which bits are set which is similar to conversion to binary and checking whether the bit is 1 or not. To check, a simple way can be
mark[(n)/32] = (mark[n/32] | (1<<(n%32))
this should work! (Reason n/32 gives the index and n%32 gives bit value, which for setting we require it as pow(2, n%32) which is same as 1<<(n%32)).
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 (here we use bitwise & operation and not && operation. a&b will give bitwise anding and we are interested in checking given bit, so 1<<(n%32) will set the number to pow(2,n%32) which is similar to only one bit equal to 1 and rest ones equal to 0, and bitwise anding will give 0 for other bits except for the desired bit for which the answer will be yes if bit was set in mark[n/32] else no).
using this your memory reduced by 32, you can reduce it by 64 also using long long(because long long uses 64 bits to store number)!
Now, adding and erasing operations. In my optimised code, you can see that first we check whether the object is already present using x[temp/32]&(1<<(temp%32)) which checks whether the corresponding bit is set of not. It return 1 if it is set else 0. So use x[temp/32]&(1<<(temp%32)) with !(not) in add operation and x[temp/32]&(1<<(temp%32)) in erase operation. Now using the properties of or and xor which are
a ‘|’ 1 = 1, a ‘|’ 0 = a, a ‘^’ 1 = !a(complement of a), a’^’ 0 = a, where ‘|’ represents or and ‘^’ represents xor).
so using x[temp/32] = (x[temp/32] | (1<<(temp%32))) sets the bits at desired position (mark it as 1) and x[temp/32] = (x[temp/32] ^ (1<<(temp%32))) flips the bit at desired position, which here will be equivalent to reseting it to 0 because this operation is performed only when the bit is set to 1 at this position (the if condition checks for this).
If you have any more doubts, you can ask in the comment section below.
Happy coding
PS: If you like the answer, upvote it and if any changes are required, do mention in comment section below.