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?

New contributor
sortedquick is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 1
    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 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 at 1:04
up vote 3 down vote accepted

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.

Your Answer

sortedquick is a new contributor. Be nice, and check out our Code of Conduct.
 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.