## Puzzle: Find integer not present in an array

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

wraith
Posts: 102
Joined: Mon Aug 06, 2007 6:58 am UTC
Contact:

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

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?
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

Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

### 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.

Flumble
Yes Man
Posts: 2248
Joined: Sun Aug 05, 2012 9:35 pm UTC

### 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:

Code: Select all

`pattern = 0for 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 0pattern 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.

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### 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.

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.

Flumble
Yes Man
Posts: 2248
Joined: Sun Aug 05, 2012 9:35 pm UTC

### 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.

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### 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: Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

### 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).

Flumble
Yes Man
Posts: 2248
Joined: Sun Aug 05, 2012 9:35 pm UTC

### 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:
But I feel stupid now: you can do an inverted binary search ("effectively doing a binary search for the most sparse range in the array" but for real this time)

Code: Select all

`lower = 0upper = 2^32for i in elements  middle = (lower+upper)/2  if lower ≤ i ≤ upper    if i < middle      lower = middle //if i is in the lower half, there must be at least one hole in the upper half    else      upper = middle //vice versa`

(there are some off-by-one errors in there, but the pseudocode looks better this way)

Nevermind, that search can end in 32 elements.

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.

PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

### 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. Tub
Posts: 472
Joined: Wed Jul 27, 2011 3:13 pm UTC

### 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.

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.