This problem can be found on Leetcode.
Given a list of integers, check if an integer in the list called
M has a value that's exactly double of a different integer
N in the list.
# assert check_if_double_exists([10, 1, 3, 6]) == True
In the list,
6 is twice the value of
3 so return
# assert check_if_double_exists([8, 5, 3]) == False
In the list, no value is twice the value of another one.
# create a function that takes as an input a list of integers # keep track of items iterated over in a set to allow for O(1) comparison lookups # assign covered_items_set to be empty set # iterate over items in input list: # if item*2 in set or item/2 in set: # return True # else: # add item to set # finished iteration and coudn't find a double or half equivalent value... # return False
def check_if_double_exists(integers_list): covered_items_set = set() for number in integers_list: if number*2 in covered_items_set or number/2 in covered_items_set: return True else: covered_items_set.add(number) return False
n be the count of items in the input list.
Time complexity is O(n) because at worst case, there's a single iteration over all values in the integer list.
Space complexity is O(n) because at worst case, all values in the integer list are added to a set of
assert check_if_double_exists([10, 1, 3, 6]) == True
assert check_if_double_exists([8, 5, 3]) == False