Least natural number.

Given a set of natural numbers N = {1,2,3,4,5 ... infinity}
And another array A with random numbers, now find the least natural number which is not present in array A.


Example:
A = {9, 8, 5, 1, 15}
here least natural number which is not present in A is 2.


Example2:
A = {5, 7, 2, 1, 4}
here least natural number which is not present in A is 3.




Approach:
1. Take a bit vector propertional to the size of array A.
if we consider the first example then our bit vector would be of size 5.
A = {9, 8, 5, 1, 15}
initially bit vector would be like:
0 0 0 0 0 
2. Go through elements in array A and set the corresponding bit vector.
A[0] = 9
since bit vector size is 5, we cant set 9th bit vector so we ignore 9.
A[1] = 8
since 8 > bit_vector_size(5), we ignore it.
A[2] = 5
we set 5th bit vector.
0 0 0 0 1
A[3] = 1
we set the 1st bit vector
1 0 0 0 1
A[4] = 15
15 > bit_vector_size(5), we ignore it.


Now our bit vector looks like:
1 0 0 0 1


And our answer is the first unset bit vector, that is 2.


time complexity: O(n) where is n is the size of array A.
space complexity: O(n) where n is the size of the array A.