Check If N and Its Double Exist — LeetCode 1346 Python Solution

The problem

Given an array arr of integers, check if there exist two indices i and j such that : i != j 0 <= i, j < arr.length arr[i] == 2 * arr[j]

This statement is abridged. Read the full problem on LeetCode.

Example

Input

arr = [10,2,5,3]

Output

true

Explanation

For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Python solution

class Solution:
    def checkIfExist(self, arr: List[int]) -> bool:
        s = set()
        for x in arr:
            if x * 2 in s or (x % 2 == 0 and x // 2 in s):
                return True
            s.add(x)
        return False

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1346. Check If N and Its Double Exist is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems