mjhjmtu

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?

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.

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(nlog 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)$.