Puzzle: Find integer not present in an array

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

Moderators: phlip, Moderators General, Prelates

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

Puzzle: Find integer not present in an array

Postby wraith » Sun Jun 23, 2019 9:09 am UTC

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

Postby Tub » Sun Jun 23, 2019 12:51 pm UTC

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.

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

Re: Puzzle: Find integer not present in an array

Postby Flumble » Sun Jun 23, 2019 1:10 pm UTC

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

User avatar
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

Postby PM 2Ring » Sun Jun 23, 2019 1:16 pm UTC

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.

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

Re: Puzzle: Find integer not present in an array

Postby Flumble » Sun Jun 23, 2019 1:27 pm UTC

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. :mrgreen: ) That gives you n+1 holes for n elements.

User avatar
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

Postby PM 2Ring » Sun Jun 23, 2019 1:45 pm UTC

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

Ok. That works. :face duly palmed: :D

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

Re: Puzzle: Find integer not present in an array

Postby Tub » Sun Jun 23, 2019 2:51 pm UTC

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) :roll:

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

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

Re: Puzzle: Find integer not present in an array

Postby Flumble » Sun Jun 23, 2019 4:00 pm UTC

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) :roll:

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". :mrgreen:

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 = 0
upper = 2^32

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


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

User avatar
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

Postby PM 2Ring » Sun Jun 23, 2019 6:06 pm UTC

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. :D

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

Re: Puzzle: Find integer not present in an array

Postby Tub » Mon Jun 24, 2019 9:06 am UTC

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.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 9 guests