Find The Missing Number In The Array
This is another classic interview question, loved by the Tech Giants. It goes as follows;
Problem Statement
From the image above, we are given an array of unsorted numbers, the size of the array is 8 and the missing number is 6. Easy enough right? What if the array is made up of a million items, then the missing number will not be easily visible.
Then we would need to write a program to simplify things. We will be using two methods, namely the Sum method and the XOR method.
Method 1: Using Sum
First we will sum up all the natural numbers, then the numbers inside the array.
We will call the Sum of natural numbers (Sn);
Sn = n(n+1)/2
We know that our n is 8, so we will substitute 8, wherever we see n.
Sn = 8(8+1)/2
Then add up 8+1 as it is within the brackets
Sn = 8(9)/2
Then multiply 8*9 before we divide, our result here.
Sn = 72/2
Sn = 36
So our sum of all natural elements is 36.
Moving on to adding all items within our array. We will call the sum of the array, Sa.
Sa =3+7+1+2+8+4+5
Sa = 30
Now that we have the sum of our array and the sum of natural number, we can determine our missing.
missing = Sn — Sa
missing = 36–30
missing = 6
Let's put this into code
def find_missing(A):
n = len(A)
total = (n+1)*(n+2)/2
Sa = sum(A)
return total - Sa
A = [3,7,1,2,8,4,5]
missing = find_missing
print(missing)
Method 2: Using XOR
XOR function works as follows;
XOR the same element gives us 0 and XOR different elements gives us 1.
Example:
A XOR A will give us 0.
A XOR B will give us 1.
Let's apply this to our array problem.
We have our array of integers;
3,7,1,2,8,4,5 and we have our natural numbers 3,7,1,2,8,4,5,6
So we will XOR all elements within our array and all elements within the natural numbers.
3^ 7^ 1^ 2^ 8^ 4^ 5 and 3^ 7^ 1^ 2^ 8^ 4^ 5^ 6
Then we XOR both these items together
3^ 3 , 7^ 7, 1^ 1, 2^ 2, 8^ 8, 4^ 4, 5^ 5
Then 6 is the lone wolf left alone, and thus this is our missing number.
