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.

Lowest positive number.

Given an array of integers (positive or negative) find the lowest positive integer NOT present in that array.


example array A = {-2, 3, 7, 9, -4, 6, 1, 2, -5}


get the count of the positive numbers, in the above example its 6
create a bit vector of size 6, then traverse the array from left to right and toggle the bit for the number which is <= 6 in the array.
[0] [0] [0] [0] [0] [0]


first positive number 3,
[0] [0] [1] [0] [0] [0]


second positive number 7 (which is greater than the size of the array (6) so we do nothing)
[0] [0] [1] [0] [0] [0]


third +ve number is 9 and as above we do nothing.
[0] [0] [1] [0] [0] [0]


fourth is 6 so we set 6th bit to 1.
[0] [0] [1] [0] [0] [1]


then its 1 and 2 so we set 1st and 2nd bit to 1.
[1] [1] [1] [0] [0] [1]


so the lowest +ve number in the array is the first bit with 0 value which is 4.