I wonder if a Bloom filter would allow you to (probably) identify the missing value and the duplicated value. Create a Bloom filter on your array, one element

I wonder if a Bloom filter would allow you to (probably) identify the missing value and the duplicated value. Create a Bloom filter on your array, one element at a time. For each element, test whether it is present in the set, and then add it to the set. By testing whether the element is already in the set, you identify the duplicated value. After creating your complete Bloom filter, then test integers 1 to N to see which is not in the set; this is your missing value. I believe this should be constant space and linear time. Above I said "probably" because there are false positives (though not false negatives).