Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Head of Career Skills Development & Coaching

*Based on past data of successful IK students

Given an unsorted set of numbers from 1 to `N`

with exactly two of them missing, find those two missing numbers.

```
{
"arr": [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.

```
{
"arr": [3, 4, 5]
}
```

Output:

```
[1, 2]
```

- Return an array with the two missing integers. The smaller number must go first.

Constraints:

- 1 <= length of the input array <= 10
^{5} - 1 <= any number in the input array <= length of the input array + 2
- Input array contains no duplicates.

Aim for an O(N) solution with constant space without modifying the input array.

We have provided two solutions for this problem. We will refer to the size of input array `arr`

as `n`

.

- 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 <= average (here,4) from the computed `sum_average`

. The resultant number is 3, which is the missing number. After this we obtain the other number, that is, 5 by subtracting 3 from the initial sum.

O(n).

We traverse the array two times.

O(1).

O(n), because of the size of input.

```
/*
Asymptotic complexity in terms of size of the given array \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/
static ArrayList<Integer> find_missing_numbers(ArrayList<Integer> arr) {
int N = arr.size() + 2;
// sum of first n numbers
long sum = (N * 1l * (N + 1)) / 2;
for (int i : arr) {
sum -= i;
}
// we find the average and store sum of first average numbers
long average = sum / 2;
long sum_average = (average * (average + 1)) / 2;
long x = 0;
//sum of all numbers from arr less than average
for (int i : arr) {
if (i <= average) {
x += i;
}
}
// the resuls sum_average - x gives the smaller missing number
// we obtain the larger number using this smaller number
int num1 = (int) (sum_average - x);
int num2 = (int) (sum - num1);
ArrayList<Integer> result = new ArrayList<>();
result.add(num1);
result.add(num2);
return result;
}
```

- 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.

O(n).

We traverse the array two times.

O(1).

O(n).

```
/*
Asymptotic complexity in terms of size of the given array \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/
static ArrayList<Integer> find_missing_numbers(ArrayList<Integer> arr) {
int N = arr.size() + 2;
int xor = 0;
// xoring all integers of array arr
for(int i : arr) {
xor ^= i;
}
//xoring all integers from 1 to n
for(int i = 1; i <= N; i++) {
xor ^= i;
}
//now xor contains the value of the xor of 2 missing numbers
//we find a setBit in this resultant xor
int setBit = 0;
for(int i = 0; i < 32; i++) {
setBit = 1 << i;
if((xor & setBit) != 0) {
break;
}
}
//we xor all integers having the corresponding bit set
int xor2 = 0;
for(int i = 1; i <= N; i++) {
if((i & setBit) != 0) {
xor2 ^= i;
}
}
//we xor all integers having the corresponding bit set in arr
for(int i : arr) {
if((i & setBit) != 0) {
xor2 ^= i;
}
}
//the resultant xor gives us one of the numbers
//we obtain the second number using this first number
int num1 = xor2, num2 = xor^num1;
if(num1 > num2) {
int temp = num1;
num1 = num2;
num2 = temp;
}
ArrayList<Integer> result = new ArrayList<>();
result.add(num1);
result.add(num2);
return result;
}
```

We hope that these solutions to finding two missing numbers have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.

Given an unsorted set of numbers from 1 to `N`

with exactly two of them missing, find those two missing numbers.

```
{
"arr": [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.

```
{
"arr": [3, 4, 5]
}
```

Output:

```
[1, 2]
```

- Return an array with the two missing integers. The smaller number must go first.

Constraints:

- 1 <= length of the input array <= 10
^{5} - 1 <= any number in the input array <= length of the input array + 2
- Input array contains no duplicates.

Aim for an O(N) solution with constant space without modifying the input array.

We have provided two solutions for this problem. We will refer to the size of input array `arr`

as `n`

.

- 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 <= average (here,4) from the computed `sum_average`

. The resultant number is 3, which is the missing number. After this we obtain the other number, that is, 5 by subtracting 3 from the initial sum.

O(n).

We traverse the array two times.

O(1).

O(n), because of the size of input.

```
/*
Asymptotic complexity in terms of size of the given array \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/
static ArrayList<Integer> find_missing_numbers(ArrayList<Integer> arr) {
int N = arr.size() + 2;
// sum of first n numbers
long sum = (N * 1l * (N + 1)) / 2;
for (int i : arr) {
sum -= i;
}
// we find the average and store sum of first average numbers
long average = sum / 2;
long sum_average = (average * (average + 1)) / 2;
long x = 0;
//sum of all numbers from arr less than average
for (int i : arr) {
if (i <= average) {
x += i;
}
}
// the resuls sum_average - x gives the smaller missing number
// we obtain the larger number using this smaller number
int num1 = (int) (sum_average - x);
int num2 = (int) (sum - num1);
ArrayList<Integer> result = new ArrayList<>();
result.add(num1);
result.add(num2);
return result;
}
```

- 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.

O(n).

We traverse the array two times.

O(1).

O(n).

```
/*
Asymptotic complexity in terms of size of the given array \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/
static ArrayList<Integer> find_missing_numbers(ArrayList<Integer> arr) {
int N = arr.size() + 2;
int xor = 0;
// xoring all integers of array arr
for(int i : arr) {
xor ^= i;
}
//xoring all integers from 1 to n
for(int i = 1; i <= N; i++) {
xor ^= i;
}
//now xor contains the value of the xor of 2 missing numbers
//we find a setBit in this resultant xor
int setBit = 0;
for(int i = 0; i < 32; i++) {
setBit = 1 << i;
if((xor & setBit) != 0) {
break;
}
}
//we xor all integers having the corresponding bit set
int xor2 = 0;
for(int i = 1; i <= N; i++) {
if((i & setBit) != 0) {
xor2 ^= i;
}
}
//we xor all integers having the corresponding bit set in arr
for(int i : arr) {
if((i & setBit) != 0) {
xor2 ^= i;
}
}
//the resultant xor gives us one of the numbers
//we obtain the second number using this first number
int num1 = xor2, num2 = xor^num1;
if(num1 > num2) {
int temp = num1;
num1 = num2;
num2 = temp;
}
ArrayList<Integer> result = new ArrayList<>();
result.add(num1);
result.add(num2);
return result;
}
```

We hope that these solutions to finding two missing numbers have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

**Attend our free webinar to amp up your career and get the salary you deserve.**

Hosted By

Ryan Valles

Founder, Interview Kickstart