About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar

Find Two Missing Numbers Problem

Problem Statement

Given an unsorted set of numbers from 1 to N with exactly two of them missing, find those two missing numbers.

Example One

Input: [6, 1, 3, 2]

Output: [4, 5]

Input has four numbers, so they must be between 1 and 6 with two missing. 4 and 5 are the missing ones. 4 is the smaller one of the two so it goes first in the output.

Example Two

Input: [3, 4, 5]

Output: [1, 2]

Notes

Input Parameters: The function has one argument, an array of integers.

Output: Return an array with the two missing integers. The smaller one must go first.

Constraints:

● 1

● 1

● Input array contains no duplicates.

Aim for an O(N) solution with constant space without

modifying the input array.

Solutions:

We provided two solutions.

1) solution1.java

● We are given an array of integers from 1 to N and two integers are missing from this array. Note that the size of the array here would be “n” which is equal to N-2.

● To find our two missing numbers, we sum all the integers from 1 to N and obtain the resultant sum. 

● From this sum, we subtract all integers present in the array. So the remainder turns out to be the sum of the two missing numbers.

● Now we take the average of that remainder.

● We know that one of the missing numbers would be less than or equal to the average, so we sum all the numbers from 1 to average and subtract all the numbers present in the array that is smaller than the average from this sum. 

● The resultant difference gives us a smaller number and subtracting this first number from the obtained sum of the missing numbers gives us the second number.

Example:

Consider the following input 

[1, 2, 4]

here we see that the sum of first 5 numbers (1 to 5) – sum of numbers present in the array is 15 – 7 = 8. The average turns out to be 8/2 = 4. Now we compute the sum from 1 to average (here, 4) and store it in variable sum_average Then we iterate over the array and subtract numbers

Time Complexity:

O(n) considering the size of the input array is n.

We traverse the array two times.

Auxiliary Space Used:

O(1).

Space Complexity:

O(n) because of the size of input.


2) solution2.java

● We will use the “exclusive or” logical operation, XOR.

● To find the two missing numbers, we take the XOR of all numbers from 1 to N and all the integers present in the array. The result gives us XOR of the two missing numbers. 

● Now a set bit in the XOR implies that one of the numbers has the corresponding bit set and the other one doesn’t. 

● So we take XOR of all numbers from 1 to N having that particular bit set and with this, we take XOR of all numbers present in the array having that particular bit set. 

● The result gives us one of the numbers.

● Taking XOR of this number with the XOR of the two missing numbers gives us the second number.

Example:

Consider the following input: [1, 2, 4].

The binary representation of the numbers 1 to 5 are

1-> 001, 2-> 010, 3-> 011, 4-> 100, 5-> 101

Taking XOR of all numbers from 1 to 5 and all numbers present in the array gives 1^2^3^4^5^1^2^4 = 3^5 = 110 in binary representation.

Now a set bit in XOR implies that one of the missing numbers has that bit set in its binary representation while the other one doesn’t. So, now we iterate over all the numbers form the array and take XOR of the numbers that have that particular bit set. Here since in 3^5 the right most bit is set, we will go through all integers present in the array and see if the rightmost bit, 1XX is set. We see that it is set for just integer 4 (in binary 100). Now we XOR this result to all integers from 1 to n whose rightmost bit is set. We see that the integers are 4 and 5. Taking the XOR of these integers with the previous one gives 4^4^5 = 5. Hence, we have obtained one of the numbers. Now taking XOR of this number with the initial XOR value yields the other number, here 3.

Time Complexity:

O(n) considering the size of the input array is n

We traverse the array two times.

Auxiliary Space Used:

O(1).

Space Complexity:

O(n) because of the size of input.