[PermMissingElem] Find the missing element in a given permutation. #hackerrank #codility #easy #timecomplexity #python

PermMissingElem.py

'''
Task description
An array A consisting of N different integers is given. The array contains integers in the range [1..(N + 1)], which means that exactly one element is missing.

Your goal is to find that missing element.

Write a function:

def solution(A)

that, given an array A, returns the value of the missing element.

For example, given array A such that:

  A[0] = 2
  A[1] = 3
  A[2] = 1
  A[3] = 5
the function should return 4, as it is the missing element.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..100,000];
the elements of A are all distinct;
each element of array A is an integer within the range [1..(N + 1)].
'''

def solution(A):
    # if empty array
    if not A: return 1
	
    # set a limit
    minimum = min(A)
    maksimum = max(A)
    
    # create a hashtable to save in distinct number and set default every number as False
    bag = {}
    for i in range(minimum, maksimum + 1): bag[i] = False
    
    # if there any number appear in 'bag' hashtable set it as True
    for i in A:
        if i in bag: bag[i] = True
    
    # if there any False value return it because is not appear in A
    for i in bag:
        if bag[i] == False: 
        	return i
 	
    # catch if all number appear in limit return 1 or maximum
	if minimum > 1:
        return 1
    else:
        return maksimum + 1