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

--

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).