Check if Double of Value Exists (via Leetcode)¶

Date published: 2020-04-12

Category: Python

Subcategory: Beginner Algorithms

Tags: 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

# 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

# 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

# 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

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

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

In [11]:

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

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