How to find a missing number in java

We make use of the operator xor(^) in finding the missing element.

Problem statement

Given an array of 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. It should run in linear time.
2. n equals to nums array length.

Hint: Use arithmetic progression, and go with the brute force approach. You can optimize the code later with a better version.

Solutions

Memoization/Hashtable approach

In this approach, we use a hashtable data structure to store all the unique elements, and we run a for-loop from 0 to nums.length + 1 which gives us the window to find the missing element.

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.

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 added is O(1).

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

Summation (Maths) approach

This uses concepts regarding n natural numbers.

Algorithm

1. We know the sum of n natural numbers are [n(n+1)/2].
2. The difference between the actual sum of the given array of elements and the sum of n natural numbers give us the missing number.

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, 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 yourself 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
    }
}

I hope you had a chance to solve the above challenge.

Let us see the solution in detail.

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.

Bit manipulation approach

We are dealing with bit manipulation and want to solve 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;

Did that clue you?

As per our above analysis, we can xor all elements together to find the missing number.

Algorithm

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

The final solution looks like this:

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 loops. So time = O(n) + O(n) => 2O(n), which is 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.

Can we further optimize the algorithm? Yes, we can reduce running two for-loops to one, and still, the algorithm runs in linear time. 🤩

Let us optimize the final solution. We are using two independent for loops to find the missing number. Now, let’s make it a single for loop.

We do two million operations if we have an array of one million integers. 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 fewer 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), and no extra space is allocated.

Finding a missing number in an array of numbers will be easy using the bit manipulation approach that takes no extra space and runs in linear time.