Python Beginner Algorithms Tutorial

# Check if Double of Value Exists (via Leetcode)

This problem can be found on Leetcode.

Problem statement:

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.

### Test Cases¶

In :
# assert check_if_double_exists([10, 1, 3, 6]) == True


In the list, 6 is twice the value of 3 so return True.

In :
# assert check_if_double_exists([8, 5, 3]) == False


In the list, no value is twice the value of another one.

### Pseudocode¶

In :
# 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:
# finished iteration and coudn't find a double or half equivalent value...
# return False


### Code¶

In :
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:
return False


### Complexity¶

Let 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 n length.

### Verify Code with Test Cases¶

In :
assert check_if_double_exists([10, 1, 3, 6]) == True

In :
assert check_if_double_exists([8, 5, 3]) == False