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.
