Created
May 30, 2022 19:26
-
-
Save awesmubarak/b819b476486b7d0c982fcc1d031a2350 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def find_missing(n_list): | |
"""Finds first missing number from list.""" | |
# At bottom of search | |
if len(n_list) == 2: | |
# If there were no missing numbers we're at the rightmost part. The | |
# numbers will still in be in sequence, 1 apart. We find the max | |
# between the lowest missing number and `1` to account for the lowest | |
# missing number being below zero. | |
if n_list[0] + 1 == n_list[1]: | |
return max(n_list[1] + 1, 1) | |
return max(n_list[0] + 1, 1) | |
# the expected value is the number's position and the actual value | |
mid_pos = int(len(n_list) / 2) | |
mid_expectation = mid_pos + n_list[0] | |
mid_reality = n_list[mid_pos] | |
# decides what direction to cut towards | |
if mid_reality > mid_expectation: | |
# missing number to left | |
missing_n = find_missing(n_list[0 : mid_pos + 1]) | |
else: | |
# missing number to right | |
missing_n = find_missing(n_list[mid_pos:]) | |
return missing_n | |
def clean_list(in_list): | |
"""Removes duplicates, sorts list""" | |
return list(sorted(set([i for i in in_list]))) | |
def main(n_list): | |
"""Calls cleaning and sorting functions""" | |
cleaned_list = clean_list(n_list) | |
if max(cleaned_list) < 1: # if all numbers below 0, return 1 | |
return 1 | |
missing_n = find_missing(cleaned_list) | |
return missing_n | |
def tests(): | |
assert main([1, 2, 4, 5, 6]) == 3 | |
assert main([1, 2, 4, 5]) == 3 | |
assert main([-1, 2, 3, 4]) == 1 | |
assert main([5, 4, 3, 1]) == 2 | |
assert main([i for i in range(100000) if i != 42]) == 42 # size: 100,000 | |
assert main([i for i in range(99900, 1000000) if i != 99956]) == 99956 | |
assert main([1, 3, 6, 4, 1, 2]) == 5 | |
assert main([1, 2, 3]) == 4 | |
assert main([-1, -3]) == 1 | |
if __name__ == "__main__": | |
tests() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment