non_neg_int.py

# Given an array arr of n unique non-negative integers, how can you most efficiently find a non-negative integer that is not in the array?

# Your solution should return such an integer or null if arr contains all possible integers.
# Analyze the runtime and space complexity of your solution.


import sys


def find_int(arr):
    """ Takes an array and returns a non-negative integer that is not in the original array. Returns null if all integers are in the array.

    Runtime: O(n)
    Spacetime: O(n)

    >>> find_int([0, 2, 1, 3, 4, 5, 11, 32, 42, 50, 100, 6])
    7

    >>> find_int([2, 4, 5, 1, 3])
    0

    >>> find_int([0, 2, 4, 5, 1, 3])
    6

    >>> find_int([0, 2, 4, 5, 1, 3, 6, 8])
    7

    >>> find_int([])
    0

    """

    arr2 = {}

    # If the length of the array is equal to the maximum allowed integers, there are no missing integers in the array.
    if len(arr) == sys.maxint:
        return None

    # Create an O(1) lookup hashtable using the integers from the array as the key, and set the value to True
    for i in range(len(arr)):
        arr2[arr[i]] = True

    # Loop through the length of the array + 1 and check if the number is a key in the hashtable. If it isn't return that number.
    for i in range(len(arr) + 1):
        if not arr2.get(i):
            return i

    return None


if __name__ == '__main__':
    import doctest
    results = doctest.testmod()

    if results.failed == 0:
        print 'ALL TESTS PASSED!'