Find Two Missing Numbers in the given Array

$\mathtt{PRE-REQUISITE}$ @ One Missing Number in an Array

Task Description

Given an array of integers which contains numbers from [1,n] except two numbers. We need to find those two missing numbers.

Example

Sample Input 1:

input_array = [1, 2, 7, 9, 3, 6, 4]

Sample Output 1:

missing numbers = 5, 8

Sample Input 2:

input_array = [2, 7, 9, 3, 6, 4, 5, 8]

Sample Output 2:

missing numbers = 1, 10

Naive Solution, Hashing Solution and Sorting Solution

If the size of input array is $n$, then we are looking for the numbers $[1,\ N]]$ inclusive where $N = n + 2$.

Similar to the Single Missing Number Problem, the Naive solution, Hashing solution and Sorting solution can be implemented in the similar fashion with similar Time and Space Complexity. The changes to be made are minor. Can you try it?

Solution 2: Using Sum of Numbers and XOR Together

Sum of numbers method and XOR of numbers method can not be applied alone to compute the two missing numbers. However, we can combine those two methods to get our result.

Principle - Part 1 (Compute Pivot)

If $x$ and $y$ be the two missing numbers, then it can be guaranteed that the two numbers will lie on the either side of a $Pivot$ number because we are talking about Unique Numbers from $1$ to $N$, and $x$ and $y$ are also Unique.

We can safely choose the $Pivot$ number to be $Pivot = (x+y)/2$.

$x+y$ can be computed by the Sum of Numbers technique we applied in Single Missing Number Problem to compute single missing number. The same method here will give us the sum of two missing numbers. After we have the sum, we can compute $Pivot = sum / 2$

Principle - Part 2 (Compute Missing Numbers)

After we have chosen the $Pivot$ number we can compute the missing number on the either sides by using XOR technique.

The missing number in the lower half can be computed by computing XOR of

1. all numbers from $1$ to $Pivot$, and
2. all numbers $\le Pivot$ in the input array

The final result will be the missing number in Lower Half.

Similarly, the missing number in the uppoer half can be computed by computing XOR of

1. all numbers from $Pivot + 1$ to $N$, and
2. all numbers $\gt Pivot$ in the input array

The final result will be the missing number in Upper Half.

Implementation

Following the implementation of above principle:

	/* File: MissingTwoNumbers.java
	* Created: 6/6/2018
	* Author: Sabbir Manandhar
	*
	* Copyright (c) 2018 WorldLingo Inc.
	*/
	/**
	* @author Sabbir Manandhar (lastname)(dot)(firstname)(at)gmail(dot)com
	* @version 1.0
	*/
	public class MissingTwoNumbers {
	public static void main(String[] args) {
	int[] input = new int[]{10, 9, 5, 6, 8, 3, 7, 4, 11, 1, 2, 13, 15};
	int[] res = find(input);
	System.out.println(res[0] + " " + res[1]);
	} // main
	//-------------------------------------------------------------------------------
	/**
	* Finds the two missing numbers in the array
	* @param input input array containing numbers [1,n] except two numbers
	* @return array of two missing numbers
	*/
	public static int[] find(int[] input) {
	long sum = findSumOfMissingNumbers(input); // find sum of missing numbers
	int pivot = (int) sum / 2;
	// Compute the missing number in lower half
	int lowerHalfXOR = 0;
	for (int i = 1; i <= pivot; i++) {
	lowerHalfXOR ^= i;
	}
	for (int i = 0; i < input.length; i++) {
	if (input[i] <= pivot) {
	lowerHalfXOR ^= input[i];
	}
	}
	// Compute the missing number in upper half
	int upperHalfXOR = 0;
	for (int i = pivot + 1; i <= input.length + 2; i++) {
	upperHalfXOR ^= i;
	}
	for (int i = 0; i < input.length; i++) {
	if (input[i] > pivot) {
	upperHalfXOR ^= input[i];
	}
	}
	return new int[]{lowerHalfXOR, upperHalfXOR};
	} // find
	//-------------------------------------------------------------------------------
	/**
	* Finds the sum of the two missing numbers in the input array
	* @param input array containing numbers [1,n] except two numbers
	* @return sum of the two missing numbers
	*/
	public static long findSumOfMissingNumbers(int[] input) {
	int n = input.length + 2;
	int expectedSum = (n * (n+1)) / 2;
	int actualSum = 0;
	for (int num : input) {
	actualSum += num;
	}
	return expectedSum - actualSum;
	} // findSumOfMissingNumbers
	//-------------------------------------------------------------------------------
	} // MissingTwoNumbers

view raw MissingTwoNumbers.java hosted with ❤ by GitHub

---

---

---