Challenge 2: Missing Number

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

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