I don't know whether this has a solution

You have an array of unique 32-bit integers in some (not necessarily sorted) order. Does there exist a linear algorithm to produce a 32-bit integer which is not present in the array?

Now I know that using the logic behind counting/pidgeonhole sort one can create an array of 2^32 booleans (using bits that's 500MB) and use it to essentially sort the input array and then find the first hole.

My question is: is there a practical solution to the original problem?

## Puzzle: Find integer not present in an array

**Moderators:** phlip, Moderators General, Prelates

### Puzzle: Find integer not present in an array

It's only when you look at an ant through a magnifying glass on a sunny day that you realize how often they burst into flames

### Re: Puzzle: Find integer not present in an array

You don't need a bitmask over 2^32 numbers. If your array contains n numbers, then you just need a bitmask over n+1 numbers. After crossing out all the wrong numbers, at least one is guaranteed to remain.

I'm wondering though: if you're allowed to modify the array, is it possible with less than O(n) additional memory?

Practically speaking, if you're assigning unique ids to some kind of object, and you want to be able to re-use ids of deleted objects, then consider using a free list, or a similar data structure that memorizes unused id ranges. That turns id assignment and deletion into O(log(n)) each.

I'm wondering though: if you're allowed to modify the array, is it possible with less than O(n) additional memory?

Practically speaking, if you're assigning unique ids to some kind of object, and you want to be able to re-use ids of deleted objects, then consider using a free list, or a similar data structure that memorizes unused id ranges. That turns id assignment and deletion into O(log(n)) each.

### Re: Puzzle: Find integer not present in an array

You could apply counting sort to one bit at a time (radix sort?), effectively doing a binary search for the most sparse range in the array:

It's in linear time because it always does 32 iterations over the array (you could take a shortcut once zeroes or ones is empty) and it only needs 4 integers. Yes, 32 iterations would mean that it only overtakes O(n log n) algorithms when the array is 2^32 long (but you can totally cheat by taking 2 bits and 4 bins at a time!) and, yes, it's actually an O(n log n) algorithm when the numbers are unbounded.

Code: Select all

`pattern = 0`

for i in [0..32)

zeroes = count array elements where first `i` bits match `pattern` and `i`th bit is 0

ones = count array elements where first `i` bits match `pattern` and `i`th bit is 1

if ones < zeroes

pattern = pattern with `i`th bit set to 1

else

pattern already has the `i`th bit set to 0

pattern now contains an unused number (or the array contains every possible number)

It's in linear time because it always does 32 iterations over the array (you could take a shortcut once zeroes or ones is empty) and it only needs 4 integers. Yes, 32 iterations would mean that it only overtakes O(n log n) algorithms when the array is 2^32 long (but you can totally cheat by taking 2 bits and 4 bins at a time!) and, yes, it's actually an O(n log n) algorithm when the numbers are unbounded.

### Re: Puzzle: Find integer not present in an array

Nice question.

How big is the array? I suspect that for smallish arrays (like n < 2^20) a sorting based approach, eg using radix sort, will be fastest.

Or maybe even a modified version of an algorithm that finds the minimum & maximum values.

Can you please elaborate? I don't get how this works. In particular, how do you associate an array entry to each bitmask bit.

How big is the array? I suspect that for smallish arrays (like n < 2^20) a sorting based approach, eg using radix sort, will be fastest.

Or maybe even a modified version of an algorithm that finds the minimum & maximum values.

Tub wrote:You don't need a bitmask over 2^32 numbers. If your array contains n numbers, then you just need a bitmask over n+1 numbers. After crossing out all the wrong numbers, at least one is guaranteed to remain.

I'm wondering though: if you're allowed to modify the array, is it possible with less than O(n) additional memory?

Can you please elaborate? I don't get how this works. In particular, how do you associate an array entry to each bitmask bit.

### Re: Puzzle: Find integer not present in an array

PM 2Ring wrote:Tub wrote:You don't need a bitmask over 2^32 numbers. If your array contains n numbers, then you just need a bitmask over n+1 numbers. After crossing out all the wrong numbers, at least one is guaranteed to remain.

Can you please elaborate? I don't get how this works. In particular, how do you associate an array entry to each bitmask bit.

One method is to take every number modulo n+1. (I think I'm feeling your facepalm. ) That gives you n+1 holes for n elements.

### Re: Puzzle: Find integer not present in an array

Flumble wrote:One method is to take every number modulo n+1. (I think I'm feeling your facepalm. ) That gives you n+1 holes for n elements.

Ok. That works. :face duly palmed:

### Re: Puzzle: Find integer not present in an array

Flumble wrote:It's in linear time because it always does 32 iterations over the array

If you're going to pretend that log(n) is a constant, why don't you go all the way? Your algorithm is bound to run in (2^32 * 32 * constant) steps, which is O(1)

PM 2Ring wrote:Tub wrote:You don't need a bitmask over 2^32 numbers. If your array contains n numbers, then you just need a bitmask over n+1 numbers. After crossing out all the wrong numbers, at least one is guaranteed to remain.

Can you please elaborate? I don't get how this works. In particular, how do you associate an array entry to each bitmask bit.

You have an array of n numbers. Take any set of n+1 numbers, and it's guaranteed to contain at least one unused number (pigeonhole). Iterate over your array, remove any number you find from the set, whatever remains in the set is an unused number.

The simplest such set is the numbers from 0 to n (inclusive), and you can implement your set with an array of bools (or a bitmask). Initializing the set is O(n), removing a number from the set is O(1), thus removing all used numbers is O(n). Finally, finding a remaining number is O(n).

### Re: Puzzle: Find integer not present in an array

Tub wrote:Flumble wrote:It's in linear time because it always does 32 iterations over the array

If you're going to pretend that log(n) is a constant, why don't you go all the way? Your algorithm is bound to run in (2^32 * 32 * constant) steps, which is O(1)

I wanted to go there, but then thought "nah, surely the array is much smaller than 2^32, so we'll pretend the input has size O(n)" and "still, the numbers are explicitly bounded, so that's constant".

Spoilered brainfart

**Spoiler:**

[edit]

Also I totally forgot that you don't have to take the numbers modulo n+1 in the pigeonholing, but you can just ignore the numbers outside the range.

Last edited by Flumble on Sun Jun 23, 2019 7:22 pm UTC, edited 2 times in total.

### Re: Puzzle: Find integer not present in an array

Tub wrote:PM 2Ring wrote:Tub wrote:You don't need a bitmask over 2^32 numbers. If your array contains n numbers, then you just need a bitmask over n+1 numbers. After crossing out all the wrong numbers, at least one is guaranteed to remain.

Can you please elaborate? I don't get how this works. In particular, how do you associate an array entry to each bitmask bit.

You have an array of n numbers. Take any set of n+1 numbers, and it's guaranteed to contain at least one unused number (pigeonhole). Iterate over your array, remove any number you find from the set, whatever remains in the set is an unused number.

The simplest such set is the numbers from 0 to n (inclusive), and you can implement your set with an array of bools (or a bitmask). Initializing the set is O(n), removing a number from the set is O(1), thus removing all used numbers is O(n). Finally, finding a remaining number is O(n).

Ah. Of course! I got confused because I was imagining something more complicated.

### Re: Puzzle: Find integer not present in an array

We have an algorithm with O(n) runtime and O(n) memory, and we have several with O(n log(n)) runtime and O(1) memory. Here's one with O(n) runtime and O(1) additional memory.

The idea is to re-organize the array such that each number x < n is at index x, with numbers >= n occupying an arbitrary position.

* every swap will move one element into place, which can happen at most n-1 times

* every loop iteration will either increase i or do a swap, the loop runs at most 2*n-1 times

All that remains is to find a free number:

Unlike the other algorithms, this one requires that the values in the array are unique.

The idea is to re-organize the array such that each number x < n is at index x, with numbers >= n occupying an arbitrary position.

Code: Select all

`let arr = [....];`

let n = arr.length;

let i = 0;

while i < n {

let value = arr[i];

if value == i || value >= n {

i++;

continue;

}

else {

swap(array[i], array[value]);

}

}

* every swap will move one element into place, which can happen at most n-1 times

* every loop iteration will either increase i or do a swap, the loop runs at most 2*n-1 times

All that remains is to find a free number:

Code: Select all

`for i in 0..n {`

if arr[i] != i {

return i;

}

}

return n;

Unlike the other algorithms, this one requires that the values in the array are unique.

### Who is online

Users browsing this forum: No registered users and 5 guests