Check If N and It's Double Exist — Day 54(Python)

Photo by David Dvořáček on Unsplash

We have been working on dynamic programming for quite some time. Today let us work on some other type of problem. Today’s question is an easy tagged question in Leetcode.

1346. Check If N and Its Double Exist

Given an array arr of integers, check if there exist two integers N and M such that N is the double of M ( i.e. N = 2 * M).

More formally check if there exist two indices i and j such that :

• i != j
• 0 <= i, j < arr.length
• arr[i] == 2 * arr[j]

Example 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: N = 10 is the double of M = 5,that is, 10 = 2 * 5.

Example 2:

Input: arr = [7,1,14,11]
Output: true
Explanation: N = 14 is the double of M = 7,that is, 14 = 2 * 7.

Example 3:

Input: arr = [3,1,7,11]
Output: false
Explanation: In this case does not exist N and M, such that N = 2 * M.

Constraints:

• 2 <= arr.length <= 500
• -10^3 <= arr[i] <= 10^3

One of the easiest ways to solve this problem is taking each number and check if it’s double is present in the array. If yes, we will return True; otherwise, we will return False. One of the edge cases to keep in mind, if we have 0 in our array, to return True, we should have another 0 in our array list.

class DoubleExist:
    def checkIfExist(self, arr: List[int]) -> bool:
        for i in range(len(arr)):
            for j in (arr[:i]+arr[i+1:]):
                if 2*arr[i] == j:
                    return True
        return False

Complexity analysis.

Time Complexity

We have two “for” loops in our solution, hence the time complexity is O(N²), where N is the number of elements in our array.

Space Complexity.

We are not using any extra data structure, hence the space complexity is O(1).

The question can be solved using the logic of Two Sum but with a twist.

We would have a dictionary that keeps track of numbers visited. We, then take each number, find if it’s double or its half is present in the dictionary keys. If yes, return True; otherwise, return False.

Let us look into the code.

import collections
class DoubleExist:
    def checkIfExist(self, arr: List[int]) -> bool:
        dict_number = collections.defaultdict(int)
        for i in range(len(arr)):
            if 2*arr[i] in  dict_number or arr[i]/2 in dict_number:
                return True
            else:
                dict_number[arr[i]] = i
        return False

Complexity analysis.

Time Complexity

We have one for loop in our solution, hence the time complexity is O(N), where N is the number of elements in our array.

Space Complexity.

We are using an additional data structure, i.e a Dictionary to store the elements, hence the space complexity is O(N).