Find The Missing Number

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)

Advertisement