DEV Community

loading...

Day-8 Check if N and It's Double exists

mridubhatnagar profile image Mridu Bhatnagar ・2 min read

This problem statement is a part of the Introduction to Data Structures Arrays-101 section in LeetCode.

Problem Statement

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

More formally check if there exists 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:

  1. 2 <= arr.length <= 500
  2. -10^3 <= arr[i] <= 10^3
Solution Approach
  1. Check if there are 0's in the array. Anything multiplied by 0 would return 0. But, remember there is a condition mentioned in the problem statement. Indices i and j should not be equal.
  2. Based on the indices statement. It can be concluded that output would be only true if the count of zero's in the array is greater than 1. Else output would be false.
  3. Create a hash table (dictionary in python) where key is the element in the array. And value is 2*(value of element).
  4. Iterate over the dictionary. And check if there exists a key whose value is equal to any value present in the dictionary.
Example:
L = [10,2,5,3]
D = {10: 20, 2: 4, 5: 10, 3: 6}

The answer returned would be true in this case as you can see there is a value 10 and key 10.
class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        result = False
        D = {}
        if (0 in arr) and (arr.count(0) > 0):
            result = True

        for x in arr:
            if x not in D and x != 0:
                D[x] = 2*x

        for value in D.values():
            result = D.get(value, None)
            if result is not None:
                result=True
                break
        return result

NOTE:

There are some edge cases to be taken care of.

  1. [0,0] - output is True
  2. [10,0,7,1] - output is False
Question

Is there a better approach to handle 0?

Discussion

pic
Editor guide