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

Image for post
Image for post
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

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

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

Software Engineer. Find me @ www.linkedin.com/in/annamariya-jt

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store