Algorithm: Two Numbers Missing

When I read Harry He's book Coding Interviews: Questions, Analysis & Solutions

Question 39 Two numbers out of n numbers from 1 to n are missing. The remaining n-2 numbers are restored in an array, not in any particular order. Please write a method (or a function) to find the missing two numbers.

He uses another array with size 2n-2, of which the first n-2 numbers are copies of numbers in the original array and others are numbers from 1 to n. All numbers except two numbers, num1 and num2, occur twice in the new array, and num1 and num2 occur only once, and convert the problem to find two numbers occurring once in an array where others occur twice.

This uses O(n) extra space, also the code to "find two numbers occurring once in an array where others occur twice" itself is complex.

The Solution

One classic idea from programming pearls is to use array index to indicate whether element exists or not. Same approach can apply here.

We scan the array two times: 

At the first time, if current element is X, and X<array.length, then negative the item at index X-1. Also remember whether array.length + 1, array.length+2 exist in the array.

Then we scan the array again, if ith value is negative, it means value (i+1) exists, we also restore its original value by negative; if ith is positive, means i+1 is missing. If we array.length + 1 or array.length+2 is not found, add them into the missing items two.

The Code

public static List<Integer> finding2Missing1ToN(int[] array) {
 // use index i to indicate whether (i+1) exists
 // if current element is X, and X<array.length, then negative the iem at
 // index X-1.
 // Also remember whether array.length + 1, array.length+2 exist in the
 // array.
 boolean plus1Exist = false, plus2Exist = false;
 for (int i = 0; i < array.length; i++) {
  int curr = array[i];
  if (curr < 0) {
   curr = -curr; // or ~curr+1
  }
  if ((curr - 1) < array.length) {
   // convert arr[curr-1] to negative value
   array[curr - 1] = -array[curr - 1];
  } else {
   if (curr == (array.length + 1)) {
    plus1Exist = true;
   } else if (curr == (array.length + 2)) {
    plus2Exist = true;
   }
  }
 }

 // scan the array again, if ith value is negative, it means (i+1)
 // exists, if
 // ith is positive, means i+1 is missing. at the same time, we change
 // negative value to absolute value to revert to array's original status.
 List<Integer> missingItems = new ArrayList<>();
 for (int i = 0; i < array.length; i++) {
  int curr = array[i];
  if (curr < 0) {
   array[i] = -array[i];
  } else {
   // i+1 is missing
   missingItems.add(i + 1);
  }
 }

 if (!plus1Exist) {
  missingItems.add(array.length + 1);
 }
 if (!plus2Exist) {
  missingItems.add(array.length + 2);
 }
 return missingItems;
}

Test Code

public void testFinding2Missing1ToN() {
 int[] array = { 3, 5, 4 };
 assertEquals(Lists.newArrayList(1, 2), finding2Missing1ToN(array));

 array = new int[] { 1, 2, 3 };
 assertEquals(finding2Missing1ToN(array), Lists.newArrayList(4, 5));

 array = new int[] { 2, 3, 4 };
 assertEquals(Lists.newArrayList(1, 5), finding2Missing1ToN(array));
}

Resources
Coding Interviews: Questions, Analysis & Solutions