Find Two Missing Numbers Problem

Find Two Missing Numbers 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

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

Example Two

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

Output:

[1, 2]

Notes

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

Constraints:

• 1 <= length of the input array <= 10⁵
• 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.

Find Two Missing Numbers Solution 1: 1St Optimal

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

Time Complexity

O(n).

We traverse the array two times.

Auxiliary Space Used

O(1).

Space Complexity

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

Code For Find Two Missing Numbers Solution 1: 1St Optimal

    /*
    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;
    }

Find Two Missing Numbers Solution 2: 2Nd Optimal

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

We traverse the array two times.

Auxiliary Space Used

O(1).

Space Complexity

O(n).

Code For Find Two Missing Numbers Solution 2: 2Nd Optimal

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