4 different ways to solve Leetcode 268: Missing Number

Question from: https://leetcode.com/problems/missing-number/

Description：

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

It is an “easy” problem but there are multiple ways to solve it. So it might be great for beginners to understand tricks that could be applied in problems on Leetcode.

Way 1: List

Sort the list, and inspect elements inside this sorted list. If the value of the next element minus the current element is larger than one, than the missing number will be the value of the current element + 1

Code (python):

However, this method is quite slow, it takes O(nlogn) to sort the list, and O(n) to go through it. The note in problem description requires you to use algorithms with linear complexity, so I suggest you not to use it although it is easy to understand.

Way 2: Dictionary

Create a set with all elements inside it, and remove the elements from that set which could be found in given list

Code(python)

O(n) to create the new list, O(n) to convert list to set, and O(n) to go through the given list, O(n) to remove all elements(except missing number) from the set

Way 3. Bitwise

Remember if num1 == num2, than num1^num2 = 0.

So we can create a list include missing number, and merge this list with nuns together using ^ operator

Code(python)

Spends O(n) to go through the new list, and O(n) to go through the given one.

You should know how the bitwise operators work before using this method. Bitwise method is quite efficient in some cases, for example, you can use

a & 1 == 0 instead of a//2 == 0 while you want to know if ‘a’ is an even number or not.

Way 4. Math trick

Simply use the sum of arithmetic progression minus the sum of the provided array.

You can also use ‘*0.5’ instead of ‘/2’ or even bitwise method to speed up the process

Only costs O(1) if you use the bitwise method instead of ‘/2’ ( number >> 1 if number & 1 == 0, else (number >>1) + 1)