Solution Review: Missing Number

Introduction

We solved the problem using lookup (hashtable) and using the mathematical formula for the sum of n natural numbers. Let's solve this more efficiently using bit-level operations with XOR.

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 the 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 combine elements 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.

Solution

The final solution looks like this:

Java

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));
    }
}

Python

def getMissingNumber(nums):
 
    res = 0
    for i in nums:
        res ^= i
 
    for i in range(0, len(nums) + 1):
        res = res ^ i
 
    return res
 

nums = [9,6,3,5,4,2,1,0,7]
print("The missing number is", getMissingNumber(nums))
 

JavaScript

const MissingNumber = array => {

    function helper (nums) {
        const n = nums.length + 1;
        let res = 0;

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

        for(const value of nums) {
            res ^= value;
        }
        return res;
    }

    return helper (array);
}

const array = [9, 6, 4, 2, 3, 5, 7, 0, 1];
console.log (`Missing element in the array is ${MissingNumber (array)}`);

C++

#include <iostream>

using namespace std;

int getMissingNumber(int arr[], int n) {

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

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

    return res;
}

int main() {
    int arr[] = {9, 6, 4, 2, 3, 5, 7, 0, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Missing element in the array is " << getMissingNumber(arr, n);
    return 0;
}

TypeScript

export const MissingNumber = (array: number[]): number => {
    function helper(nums: number[]): number {
        const n: number = nums.length + 1;
        let res: number = 0;

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

        for (const value of nums) {
            res ^= value;
        }
        return res;
    }

    return helper(array);
}

const array: number[] = [9, 6, 4, 2, 3, 5, 7, 0, 1];
console.log(`Missing element in the array is ${MissingNumber(array)}`);

Complexity analysis

Time complexity: O(n)We are using two independent loops. So time = O(n) + O(n) => 2*O(n), which is O(n).

Where, n is the number of elements in the array since we must 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

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.

Here the code has fewer lines compared to the one above. Let’s look at the below code:

Java

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));
    }
}

Python

def MissingNumber(nums):
    missing=len(nums)
    for i in range(0,len(nums)):
        missing ^= i ^ nums[i]
    return missing
nums=[9,6,4,2,3,5,7,0,1]
print("Missing element in the array is: ",MissingNumber(nums))

JavaScript

const MissingNumber = array => {

    function helper (nums) {
        let missing = nums.length;

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

    return helper (array);
}

const array = [9, 6, 4, 2, 3, 5, 7, 0, 1];
console.log (`Missing element in the array is ${MissingNumber (array)}`);

C++

#include <iostream>

using namespace std;

int helper(int arr[], int n) {
    int m = n;
    for (int i = 0; i < n; i++)
        m ^= i ^ arr[i];
    return m;
}

int main() {
    int arr[] = {9, 6, 4, 2, 3, 5, 7, 0, 1};
    int n = 9;
    cout << "missing element is : " << helper(arr, n);
    return 0;
}

TypeScript

export const MissingNumber = (array: number[]): number => {
    function helper(nums: number[]): number {
        let missing: number = nums.length;

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

    return helper(array);
}

const array: number[] = [9, 6, 4, 2, 3, 5, 7, 0, 1];
console.log(`Missing element in the array is ${MissingNumber(array)}`);

Complexity analysis

Time complexity: O(n): Where, n is the number of elements in the array, as we must 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 linearly.