Register for our webinar

How to Nail your next Technical Interview

1 hour
Loading...
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
By sharing your contact details, you agree to our privacy policy.
Step 1
Step 2
Congratulations!
You have registered for our webinar
check-mark
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
check-mark
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.
close-icon
Iks white logo

You may be missing out on a 66.5% salary hike*

Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Iks white logo
Help us know you better!

How many years of coding experience do you have?

Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Iks white logo

FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Thank you! Please check your inbox for the course details.
Oops! Something went wrong while submitting the form.
closeAbout usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career
close

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 <= 105
  • 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:

‍To learn more, register for the FREE webinar.

Try yourself in the Editor

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

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 <= 105
  • 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:

‍To learn more, register for the FREE webinar.

Worried About Failing Tech Interviews?

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

Ryan-image
Hosted By
Ryan Valles
Founder, Interview Kickstart
blue tick
Accelerate your Interview prep with Tier-1 tech instructors
blue tick
360° courses that have helped 14,000+ tech professionals
blue tick
100% money-back guarantee*
Register for Webinar

Recommended Posts

All Posts