How To Solve Missing Number Problem In Java, An Amazon Interview Question

Introduction

We make use of XOR principles in finding a missing element.

Let’s see how to achieve this using the XOR operator.

Problem statement

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Input: nums = { 9, 6, 4, 2, 3, 5, 7, 0, 1 }

Output: 8

Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Constraints:

1. Do it in Linear Complexity.

2. n == nums.length

Hint: Use arithmetic progression and go with the Brute force approach. Then optimize it.

Solution

Approach 01: Hashtable

This one is better than the one above as we are iterating over all the elements once with O(n)extra memory space.

Algorithm

This algorithm is almost identical to the Brute force approach, except we first insert each element of nums into a Set, allowing us to later query for containment in O(1) time.

Code

import java.util.HashSet;

class MissingNumber {
    private static int helper(int[] nums) {
        HashSet<Integer> set = new HashSet<Integer>();

        for (int num : nums) {
            set.add(num);
        }

        int n = nums.length + 1;

        for (int i = 0; i < n; i++) {
            if (!set.contains(i)) {
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

Complexity analysis

Time complexity: O(n), the time complexity of for loops is O(n) and the time complexity of the hash table operation add is O(1).

Space complexity: O(n), the space required by the hash table is equal to the number of elements in nums.

Approach 01: Maths

This uses concepts regarding n natural numbers.

Algorithm

1. We know the sum of n natural numbers is [n(n+1)/2] ​
2. Now, the difference between the actual sum of the given array elements and the sum of n natural numbers gives us the missing number.

Code

class MissingNumber {
    private static int helper(int[] nums) {
        int n = nums.length;
        int expectedSum = ((n * (n + 1)) / 2);

        int actualSum = 0;

        for (int num : nums) {
            actualSum += num;
        }

        return expectedSum - actualSum;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

Complexity Analysis

Time complexity: O(n), the time complexity of the for loop is O(n).

Space complexity: O(1), as we are not using any extra space.

Coding exercise

First, take a closer look at these code snippets above and think of a solution.

Your solution must use the ^ operator.

This problem is designed for your practice, so try to solve it on your own first. If you get stuck, you can always refer to the solution provided in the solution section. Good luck!

class Solution{
    public static int missingNumber(int[] nums){
       // Write - Your - Code- Here

        return -1; // change this, return missing element; if none, return -1
    }
}

The solution is explained below.

We solved the problem using lookup (Memoization/Hashtable) and using the mathematical formula for the sum of n natural numbers, Let's solve this more efficiently using bit-level operations with ^ or xor.

Solution review: Bit manipulation

We are dealing with bit manipulation and want to solve all of these problems with Bitwise operators.

Concepts

If we take XOR of 0 and a bit, it will return that bit.

a ^ 0 = a

If we take XOR of two same bits, it will return 0.

a ^ a = 0

For n numbers, the math below can be applied.

a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b;

For example:

1 ^ 5 ^ 1 = (1 ^ 1) ^ 5 = 0 ^ 5 = 5;

So, we can XOR all bits together to find the unique number.

Algorithm

1. Initialize a variable, res = 0.

2. Iterate over array elements from 0 to length + 1 and do ^ of each with the above-initialized variable.

Iterate over all the elements and store the value in the variable.

Code

Here is the logic for this solution.

class MissingNumber {
    private static int helper(int[] nums) {
        int n = nums.length + 1;
        int res = 0;

        for (int i = 0; i < n; i++) {
            res ^= i;
        }

        for (int value : nums) {
            res ^= value;
        }
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

Complexity analysis

Time complexity: O(n), we are using two independent for loops. So Time = O(n) + O(n) => O(n).

Where, n is the number of elements in the array, since we need to iterate over all the elements to find a missing number. So, the best and the worst-case time is O(n).

Space complexity: O(1), the space complexity is O(1). No extra space is allocated.

Optimization

Let us optimize the last solution.

We are using two independent for loops to find the missing number.

Now, let’s make it a single for loop. If we have an array of one million integers, then we do two million operations.

We can reduce the number of operations into n, where n is the array’s size.

Let’s look at the below code.

class MissingNumber {
    private static int helper(int[] nums) {
        int missing = nums.length;

        for (int i = 0; i < nums.length; i++) {
            missing ^= i ^ nums[i];
        }
        return missing;
    }

    public static void main(String[] args) {
        int[] nums = {9, 6, 4, 2, 3, 5, 7, 0, 1};
        System.out.println("Missing element in the array is " + helper(nums));
    }
}

Here the code has less lines compared to the one above.

Complexity analysis

Time complexity: O(n): Where, n is the number of elements in the array, as we need to iterate over all the elements to find a missing number. So, the best, worst-case time is O(N).

Space complexity: O(1), the space complexity is O(1), no extra space is allocated.

---

Learn more

I’ve got a course on bit manipulation that is loved by more than 200k+ programmers. Find it here: Master Bit Manipulation for Coding Interviews.

In this course, we learn how to solve problems using bit manipulation, a powerful technique that can be used to optimize our algorithmic and problem-solving skills. The course has simple explanations with sketches, detailed step-by-step drawings, and various ways to solve problems using bitwise operators.

Comments

[Jon Randy 🎖️]

Javascript, using reduce:

const missingNumber = nums => nums.reduce((m,n,i)=>m^n^i, nums.length)

[Gopi Gorantala]

This is cool.. I love the single line snippets 😍.. but in coding interviews tech giants and fewer companies expect you to write an algorithm instead re-use an existing built-in function/methods.

[peerreynders]

In principle reduce can be viewed as a shorthand for recursion over a collection

const xorKVs = (values, key, n) =>
  key >= 0 ? xorKVs(values, key - 1, n ^ key ^ values[key]) : n;
const xorKVAll = (values) => xorKVs(values, values.length - 1, values.length);

console.log(xorKVAll([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8

while recursion is immutable iteration

console.log(xorKVAll([9, 6, 4, 2, 3, 5, 7, 0, 1])); // 8

function xorKVAll(values) {
  let n = values.length; // from range of values [0, n]
  for (let key = n - 1; key >= 0; key -= 1) n ^= key ^ values[key];

  return n;
}

While some people using reduce() (foldl()) may not be comfortable with the recursive alternative, they'll more than likely be capable of formulating the iterative version.

I suspect the question has less to do with the actual solution implementation but more with determining whether the candidate

• is aware of the properties of bitwise XOR operation
• has the insight that the keys/indices (and the length) of the array provide a "free" master set of values that should be in the array - creating the opportunity to leverage the properties of bitwise XOR in the first place.

Though I also suspect that the minority of candidates actually arrive at this from first principles but only hit on this because of interview preparation.

So really what is largely being assessed is

• whether the candidate could be bothered to prepare for the interview
• whether the candidate happened upon this exact problem during preparation
• whether the candidate could recall enough to reconstruct the solution

So being asked to tweak the solution and being able to adapt is really the core of the interview.

[Gopi Gorantala]

Thanks for the notes 🤩, they’re helpful to me! ☺️

You’re right about the assessments of candidates. It’s the thought process and different approaches the candidates think of… that’s what interviewers look for!!

[Jon Randy 🎖️]

I somehow don't think you're going to be penalised for using stuff like map, filter, and reduce - these are pretty much cornerstones of functional programming

[Jon Randy 🎖️]

I would actually look down upon a candidate reinventing any of the above methods, as the resulting code would likely be less efficient - and they've also demonstrated a lack of knowledge of the language.

The key here is the XOR stuff... the loops and other things are just fluff.

[Gopi Gorantala]

Yup.. the key is xor. Functional programming is quite fun. I got interviewed at Amazon last December, I was asked to implement a longest connected nodes for a binary tree.. it was easy and I did it using iteration first, she asked me to go for recursion and I did. next, she asked me to try with another approach. So the point is, if you implement the solution one way, they tweak it ask you for some other cases, what if that and what if this happens on the writtten algorithm. The point is, we need to train our brain for all possible solutions and optimize them 😉