The problem is as follows:

We are given a list of n-1 integers and these integers are in the range of 1 to n.

There are no duplicates in the list. One of the integers is missing in the list.

Give an algorithm to find the missing integer.

Sample Input: [1,2,4,6,3,7,8]

Sample Output: 5

arr = [1,2,4,6,3,7,8]
'''solution using brute force
Complexity Time: O(n^2) Space = O(1)'''
def findMissing(arr):
missingNumber = -1
for i in range(1,len(arr)):
if i in arr:
pass
else:
missingNumber = i
return missingNumber
print findMissing(arr)
'''solution using sorting
Complexity Time: O(nlogn) Space:O(1)'''
def findMissingUsingSorting(arr):
missingNumber = -1
arr.sort()
for i in range(len(arr)):
if arr[i] == i+1:
pass
else:
missingNumber = i+1
break
return missingNumber
print findMissing(arr)
'''solution using hashing technique
Complexity Time: O(n) Space O(n)'''
def findMissingUsingHashing(arr):
numberDict = {}
missingNumber = -1
for i in range(len(arr)+1):
numberDict[i+1] = 0
for i in arr:
numberDict[i] = 1
for i in numberDict:
if numberDict[i] == 0:
missingNumber = i
return missingNumber
print findMissing(arr)

### Like this:

Like Loading...

*Related*