Say you have an array with integer sequential numbers in it, but there are missing numbers in it. How to find what are those numbers? Assume the array is already sorted ascendant.
Solution
On the Internet, I found cases where there is only one number missing and the approach is to do sum of the numbers and verify if the sum S equals to n*(n+1)/2. S(n) = n + (n-1) + (n-2) + .... + 0. If not equal, then difference is equal to the missing number, because S + missing number must be = n*(n+1)/2.
def MissingSingleNum(A):
sum = 0
n = A[len(A)-1]
for i in A:
sum = sum + i
computed = n*(n+1)/2
if sum != computed:
return computed - sum
else:
return "None"
A = [1,2,4,6,7,8]
MissingSingleNum(A)
Some weaknesses of the above algorithm it cannot find more than one missing number and numbers in the array should not be negative. So in case of [-3,-2,-1,0,1,2,3,5], the computed sum is 8*(8+1)/2 = 36 (remember n is = number of elements in the array), where it is supposed to be 5, and the missing number is 4. The same issue for A=[0,1,2,4,6,7,8] where [3,5] are missing, the algorithm cannot find that either.
To solve multiple missing numbers, we cannot use the above approach. Basically we need to classify the cases. Say we have A = [-2, 0, 2, 6, 12]
By looking at it, we know for the range [-2..12], the missing numbers are [-1,1,3,4,5,7,8,9,10,11].
One approach is, we scan from the lowest number to highest number and see if there are missing sequential numbers. Because we already know the array is sorted, we scan a range from A[0] to A[len-1] and check against a dictionary we build (see below). The dictionary (or hash table) is very fast, it's only O(1) when the numbers are unique.
def IsExist(d,k):
try:
d[k]
return True
except:
return False
def MissingNumbers(A):
n = len(A)
miss = []
d = {}
j = 0
for e in A:
d[e] = j
j = j+1
for i in range(A[0], A[n-1]):
try:
if not IsExist(d,i):
miss.append(i)
except:
pass
return miss
Test:
A[] = [0, 2, 4, 5, 6]
Missing numbers: [1, 3]
A[] = [-2, 0, 5, 16]
Missing numbers: [-1, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
A slightly better way or an improvement of above code is the factthat we can use <array>.index(value) to check if a value exists in the array (so no need to use dictionary).
def MissingNumbers(A):
n = len(A)
miss = []
for i in range(A[0], A[n-1]):
try:
if A.index(i):
pass
except:
miss.append(i)
return miss
Solution
On the Internet, I found cases where there is only one number missing and the approach is to do sum of the numbers and verify if the sum S equals to n*(n+1)/2. S(n) = n + (n-1) + (n-2) + .... + 0. If not equal, then difference is equal to the missing number, because S + missing number must be = n*(n+1)/2.
def MissingSingleNum(A):
sum = 0
n = A[len(A)-1]
for i in A:
sum = sum + i
computed = n*(n+1)/2
if sum != computed:
return computed - sum
else:
return "None"
A = [1,2,4,6,7,8]
MissingSingleNum(A)
Some weaknesses of the above algorithm it cannot find more than one missing number and numbers in the array should not be negative. So in case of [-3,-2,-1,0,1,2,3,5], the computed sum is 8*(8+1)/2 = 36 (remember n is = number of elements in the array), where it is supposed to be 5, and the missing number is 4. The same issue for A=[0,1,2,4,6,7,8] where [3,5] are missing, the algorithm cannot find that either.
To solve multiple missing numbers, we cannot use the above approach. Basically we need to classify the cases. Say we have A = [-2, 0, 2, 6, 12]
By looking at it, we know for the range [-2..12], the missing numbers are [-1,1,3,4,5,7,8,9,10,11].
One approach is, we scan from the lowest number to highest number and see if there are missing sequential numbers. Because we already know the array is sorted, we scan a range from A[0] to A[len-1] and check against a dictionary we build (see below). The dictionary (or hash table) is very fast, it's only O(1) when the numbers are unique.
def IsExist(d,k):
try:
d[k]
return True
except:
return False
def MissingNumbers(A):
n = len(A)
miss = []
d = {}
j = 0
for e in A:
d[e] = j
j = j+1
for i in range(A[0], A[n-1]):
try:
if not IsExist(d,i):
miss.append(i)
except:
pass
return miss
Test:
A[] = [0, 2, 4, 5, 6]
Missing numbers: [1, 3]
A[] = [-2, 0, 5, 16]
Missing numbers: [-1, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
def MissingNumbers(A):
n = len(A)
miss = []
for i in range(A[0], A[n-1]):
try:
if A.index(i):
pass
except:
miss.append(i)
return miss
