Performance when searching for missing numbers in array

Given is a list containing all but 2 numbers between 1-20 (randomly ordered). I need to find those 2 numbers.

This is the (working) program I ca开发者_运维技巧me up with:

public static void main(String[] args) {
    int[] x= {1,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19};
    ArrayList al= new ArrayList();
    Map map= new HashMap();
    for(int i=0;i<x.length;i++)
    {
        map.put(x[i], x[i]);
    }
    for(int i=1;i<=20;i++)
    {
        if(map.get(i)==null)
            al.add(i);
    }
    for(int i=0;i<al.size();i++)
    {
        System.out.println(al.get(i));
    }
}

I would like to know if the program is good from a performance point of view (memory and bigO(n))?

You don't need a map. Just an additional boolean array with size 20.

for (int i = 0; i < input.length; i++)
   arr[input[i]] = true;

for (int i = 1; i <= 20; i++)
   if (arr[i] == false) {
      //number `i` is missing
   }     

Now I will expose a straightforward math solution.

First sum all numbers in the array. For example you have 5, 1, 4 for the numbers from 1, 2, 3, 4, 5. So 2 and 3 are missing. We can find them easily with math.

5 + 1 + 4 = 10
1 + 2 + 3 + 4 + 5 = 15

So we know x + y = 15 - 10 = 5 Now we will get a second equation:

1 * 4 * 5 = 20
1 * 2 * 3 * 4 * 5 = 120
=> x * y = 120 / 20 = 6

So:

x + y = 5
x * y = 6

=> x = 2, y = 3 or x = 3, y = 2 which is the same.

So x = 2, y = 3

Another option would be to use a BitSet where each bit is set for the corresponding number in the array.

Your code runs at O(n) due to the map.put operation. The for loop below that will run at O(n) at the worst case too, so in total, your whole function runs at O(n).

You can optimise your code further. For example, you are using additional memory. To improve on this, you need to come up with 2 eqns to deduce missing numbers x and y.

Eqn1: Summation(1 till 20) = n*(n+1)/2 Add all numbers in array and store in temp. x+y = n*(n+1)/2 - temp

Eqn2: Multiply(1 till 20) = n! Multiply all numbers in array and store in temp. x*y = temp / n!

Solve the equations to get x and y.

So this will run O(n) without much memory.

It should not be anything worse than linear time O(n): one run to populate a flag array, and a second run to check the flag array.