Last week, there was a discussion in my team on the problem of finding missing number(s). We had different thoughts and approaches and thus I thought to share it across.
Problem statement was something like:
– An array of size (n) has numbers from 1 to (n+1). Find the missing one number.
– An array of size (n) has numbers from 1 to (n+2). Find the missing two numbers.
First thought …
Keep track of numbers found while traversing. At the end, use it to find the missing number. So kind of brute force approach.
We can maintain a hash or a boolean array of n size and keep on updating the hash or the array index location based on number found while traversing. Use it now to find the missing number. It would cover both one as well as two missing numbers case.
This would have two traversals of n (one for filling in the structure and another to find the missing one). Thus overall, time complexity of O(n). This would need an extra space to keep track of all numbers found and thus a space complexity of O(n).
Q: Now, can we avoid extra space or two times traversal?
Second thought …
We know how to calculate the sum of n natural numbers, i.e.: n*(n+1)/2. With it, we can traverse the given array and keep a sum of all numbers. Difference of the sum from formula to sum found would give us the missing number. Nice!
# Keep track of sum
def sumOfGivenNumbers(nos, n):
sum = 0
# calculate sum
for i in range(0, n):
sum += nos[i]
return sum
# Input
numbers = [4, 2, 1, 6, 5, 7]
# number range
n = len(numbers) + 1
expectedSum = n*(n+1)/2
numbersSum = sumOfGivenNumbers(numbers,len(numbers))
print('Missing number:', expectedSum - numbersSum)
# Output
# Missing number: 3.0
This would help is solve one missing number in single traversal, thus time complexity of O(n). No extra space was used and thus space complexity of O(1).
Q: Can we extend this to two missing numbers now?
Yes, we can extend it. Along with sum, we can also use the product of n natural number as an expression. With it, we will have two equations and two numbers to find:
Missing1 = x1
Missing2 = x2
Sum of provided numbers = N1
Sum of n Natural numbers = N
Product of provided numbers = P1
Product of n Natural numbers = P
x1 + x2 + N1 = N
x1 * x2 * P1 = P
We can solve it to find the two missing numbers. It does have the quadratic flavor associated though. It maintains the time complexity as O(n) and space complexity as O(1). Nice!
Q: Does the solution help with large integers? Think of possible overflow?
Third thought …
Let’s look at possible way for 1 missing number first.
We will traverse through all the numbers of the array. While doing so, maintain a number that would be sum of all numbers traversed so far reduced by sum of all the indexes traversed (+1 if index starts from 0). It is still making use of n natural numbers (in form of indexes) to keep a check on sum to a defined limit.
# Keep track of sum
def getMissingNumber(nos, n):
sum = 0
# calculate sum
for i in range(0, n):
sum += (i+1)
sum -= nos[i]
# last number to add from n+1 natural nos.
return sum+n+1
# Input
numbers = [4, 2, 1, 6, 5, 7]
missingNumber =getMissingNumber(numbers,len(numbers))
print('Missing number:', missingNumber)
# Output
# Missing number: 3.0
This looks good and we maintain the same complexities along with solving for overflow.
We can probably try a similar thing for two missing numbers where we keep on multiple and divide the traversed number by index but it still could have overflow issues in worst case. Further, there could be round off issues.
Fourth thought …
Looking more, it seems we can make use of XOR operation to find the missing numbers. We can make use of XOR’s property to nullify the duplicate pair. We will take XOR of provided numbers and XOR of natural numbers. Combining both again with XOR will leave with missing numbers XOR output.
For one missing number, this would be easy and covers all the hurdles discussed earlier keeping same performance.
# Keep track of XOR data
def getMissingNumber(nos, n):
x1 = nos[0]
xn = 1
# start from second
for i in range(1, n):
x1 = x1 ^ nos[i]
xn = xn ^ (i+1)
# last number to XOR
xn = xn ^ (n+1)
# find the missing number
return x1 ^ xn
# Input
numbers = [4, 2, 1, 6, 5, 7]
missingNumber =getMissingNumber(numbers,len(numbers))
print('Missing number:', missingNumber)
# Output
# Missing number: 3.0
For two missing numbers, using a similar logic of XOR above, we will have an output of XOR value of both missing numbers. Now, given the XOR value will not be zero, the XOR corresponding valid bit in missing1 and missing2 must be different to make it “1”.
# Keep track of XOR data
def getTwoMissingNumber(nos, n):
x1 = nos[0]
xn = 1
# start from second
for i in range(1, n-2):
x1 = x1 ^ nos[i]
xn = xn ^ (i+1)
# last numbers to XOR
xn = xn ^ (n-1) ^ (n)
# XOR of two missing numbers
# Any set bit in it must be
# set in one missing and
# unset in other missing number
XOR = x1 ^ xn
# Get a rightmost set bit of XOR
set_bit_no = XOR & ~(XOR-1)
# Divide elements in two sets
# by comparing rightmost set bit of XOR
# with bit at same position in each element.
x = 0
y = 0
for i in range(0,n-2):
if nos[i] & set_bit_no:
# XOR of first set in nos[]
x = x ^ nos[i]
else:
# XOR of second set in nos[]
y = y ^ nos[i]
for i in range(1,n+1):
if i & set_bit_no:
# XOR of first set in nos[]
x = x ^ i
else:
# XOR of second set in nos[]
y = y ^ i
print ("Missing Numbers: %d %d"%(x,y))
return
# Input
numbers = [4, 2, 1, 6, 7, 5]
# total length will be provided count+2 missing ones
getTwoMissingNumber(numbers, len(numbers) + 2)
# Output
# Missing Numbers: 3 8
This overcomes the overflow issue and was easier to solve (compared to solving a quadratic equation). Though it took more than one traversal, overall it maintains the time complexity as O(n) and space complexity as O(1). Nice!
Closure …
There could be multiple ways to solve for one or more missing numbers. One can look at it based on ease and need.
Keep solving!
