Find the smallest missing number with Duplicates

Question

This is an interview question, but I couldn't solve it in time, so posting it here:

Given a sorted array of n integers where each integer is in the range from 0 to m-1 and m > n. Find the smallest number that is missing from the array.

Examples Input: {0, 1, 2, 6, 9}, n = 5,m = 10 Output: 3

Input: {4, 5, 10, 11}, n = 4, m = 12 Output: 0

The code for this is as follows:

int findFirstMissing(int array[], int start, int end) {

    if(start  > end)
      return end + 1;

    if (start != array[start])
      return start;

    int mid = (start + end) / 2;

    if (array[mid] > mid)
      return findFirstMissing(array, start, mid);
    else
      return findFirstMissing(array, mid + 1, end);
}

Now, the question is that input array can have duplicates also:

input = [0, 1, 1, 2, 3, 3, 4, 5, 5, 7]

output = 6

How do I solve it efficiently? What kind of optimizations can be applied?

score 0 · Answer 1 · answered Jun 05 '14 at 13:18

0

It can be easily proved that you have to this in O(n) time, as you can't distinguish without checking every single value two tables:

1,2,_3_,4,5,7

and

1,2,_2_,4,5,7

answered Jun 05 '14 at 13:18

Lukasz

186
3

Alexey Malev · Answer 2 · 2014-06-05T13:24:48.150

0

This solution works in O(N) time and uses O(1) additional memory:

public class Test {
    public static void main(String[] args) {
        int m = 5;
        int[] data = new int[] {0, 1, 1, 2, 3, 3, 4, 5};

        int current = 0;
        for (int i = 0; i < data.length; ++i) {
            if (current == data[i]) {
                current++;
            }
        }

        if (current >= m) {
            System.out.println("All is here");
        } else {
            System.out.println(current);
        }
    }
}

Note: n is actually ignored, I used data.length instead.

edited Jun 05 '14 at 13:24

answered Jun 05 '14 at 13:19

Alexey Malev

6,408
4
34
52

Can we have any better complexity? Any optimizations? – user3156792 Jun 05 '14 at 13:25
No, complexity cannot be lower than O(N), because you need to read all the numbers of the array at least once, this is O(N). You can do an optimization and stop iterating over an array if `current` is already equals to `m` - in that case we can say that everyone is here already. – Alexey Malev Jun 05 '14 at 13:27

score 0 · Answer 3 · edited Jun 05 '14 at 13:36

Solution

    public static void main(String[] args) {
    Collection<Integer> input = new LinkedList<Integer>(Arrays.asList(10, 9, 7, 6, 5, 4, 3, 2, 1));
    NavigableSet<Integer> sortedOriginal = new TreeSet<Integer>(input);

    NavigableSet<Integer> numbers = new TreeSet<Integer>();
    for(int i=sortedOriginal.first();i<=sortedOriginal.last();i++){
        numbers.add(i);
    }

    for(Integer x : numbers){
        if(!sortedOriginal.contains(x)){
            System.out.println(x);
            break;
        }
    }
}

Find the smallest missing number with Duplicates

3 Answers3