# Outputting numbers within a range that are not in a list

How could you design an efficient algorithm that uses the least amount of memory space and outputs, in ascending order, the list of integers in the range 0..255 that are not in a randomly generated list of 100 integers?

The aim is to output the number of such integers, and determine if the randomly generated list of 100 integers included any repeats.

The naive approach would be to compare each number from 0 to 255 against the list of 100 integers. This would not be very efficient.

What would be a more efficient approach to solve this?

• Honestly, if you really only have 100 integers in the list and they're really only between 0 and 255, there's probably not much point trying to optimize this. For such a small task, any algorithm that works will be adequate, unless you need to run it many, many times. – David Richerby Nov 8 '18 at 23:59
• So if you use one bit per value (256), in one loop set bit for each integer, output that value if the bit is set and then in second pass output values for bits that are 0, is it sufficient? – Evil Nov 9 '18 at 1:04

Let $$n$$ be the number of random elements (in your case $$n = 100$$), and let $$k$$ be the total number of elements (in your case $$k = 256$$). Draconis gave a solution in time and space $$O(k)$$.

Another possible solution uses time $$O(n\log n + k)$$ and space $$O(n)$$:

1. Sort the input elements $$A[1],\ldots,A[n]$$.

2. Let $$i \gets 1$$.

3. For $$j \gets 0,\ldots,k-1$$:

• If $$i > n$$ or $$A[i] \neq j$$: output $$j$$.

• While $$i \leq n$$ and $$A[i] = j$$: let $$i \gets i + 1$$.

This is strictly better than the other solution if $$n = o(k/\log k)$$.

Facetious answer: all the sizes involved are constant, so a straightforward algorithm for this will run in $$O(1)$$.

Serious answer: with such small numbers involved, getting too elaborate may just slow you down. Simplicity is your friend.

let found be an array [0..255]
found ← [false, false, false...]

for i ← [1..100]:
value ← A[i]
if found[value] is true:
there was a repeat
found[value] ← true

for j ← [0..255]:
if found[value] is false:
j was not in the list


This runs in $$O(n+k)$$ time and $$O(k)$$ space (where $$n$$ is the number of elements in the array and $$k$$ is the maximum size of those elements). I don't believe it's possible to do better.