get_different_number.py

# PRAMP - Getting a Different Number
# Given an array arr of unique nonnegative integers, implement a function getDifferentNumber that finds the smallest nonnegative integer that is NOT in the array.

# Even if your programming language of choice doesn’t have that restriction (like Python), assume that the maximum value an integer can have is MAX_INT = 2^31-1. So, for instance, the operation MAX_INT + 1 would be undefined in our case.

# Your algorithm should be efficient, both from a time and a space complexity perspectives.

# Solve first for the case when you’re NOT allowed to modify the input arr. If successful and still have time, see if you can come up with an algorithm with an improved space complexity when modifying arr is allowed. Do so without trading off the time complexity.

# Analyze the time and space complexities of your algorithm.

# input:  arr = [0, 1, 2, 3]
# output: 4


#==== Solution 0 (O(n^2) time complexity, O(1) space complexity) ====
def get_different_number(arr):

    for i in range(len(arr)):
        if i not in arr:
            return i
    
    return len(arr)


#==== Solution 1 (O(nlog(n) time complexity, O(n) space complexity) ====
def get_different_number(arr):
    
    arr_new = sorted(arr)

    for i in range(len(arr_new)):
        if arr[i] != i:
            return i
    
    return len(arr)

#==== Solution 2 (O(n) time complexity, O(n) space complexity) ====
def get_different_number(arr):

    arr_set = set(arr)

    for i in range(len(arr)):
        if i not in arr_set:
            return i
    
    return len(arr)

#==== Solution 3 (O(n) time complexity, O(1) space complexity) ====
def get_different_number(arr):

    for i in range(len(arr)):
        required_idx = arr[i]
        while arr[required_idx] != i and required_idx < len(arr):
            arr[required_idx], arr[i] = arr[i], arr[required_idx]
    
    for i in range(len(arr)):
        if i not in arr:
            return i
    
    return len(arr)