def missing_int_o_n(a): ''' Solve it with Pigeonhole principle. There are N integers in the input. So for the first N+1 positive integers, at least one of they must be missing. ''' # We only care about the first N+1 positive integers. # occurrence[i] is for the integer i+1. occurrence = [False] * (len(a) + 1) for item in a: if 1 <= item <= len(a) + 1: occurrence[item - 1] = True # Find out the missing minimal positive integer. for index in range(len(a) + 1): if not occurrence[index]: return index + 1