Python Beginner Algorithms Tutorial

# Check if Double of Value Exists (via Leetcode)

- April 12, 2020
- Key Terms: functions, loops, sets

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 [4]:

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

In the list, `6`

is twice the value of `3`

so return `True`

.

In [5]:

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

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

### Pseudocode¶

In [6]:

```
# 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
```

### Code¶

In [9]:

```
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
```

### 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 [10]:

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

In [11]:

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