Is Check If N and Its Double Exist easy or hard?

LeetCode classifies this problem as Easy. The main skill tested is recognizing that a pair relationship can be detected with a hash set instead of checking every pair, reducing the complexity from O(n^2) to O(n).

Check If N and Its Double Exist Python/Java solution

Python solutions typically use a built-in set for O(1) lookups, while Java implementations use HashSet . Both follow the same logic: iterate through the array, check for double or half in the set, and insert the current value.

How to solve Check If N and Its Double Exist in O(n)?

Traverse the array while storing seen numbers in a hash set. For each value x, check if 2*x exists in the set or if x is even and x/2 exists. If either condition is true, a valid pair has been found. Insert x into the set and continue scanning.

What is the best approach for Check If N and Its Double Exist?

The most efficient approach uses a hash set. Iterate through the array and check whether 2*x or x/2 already exists in the set before inserting the current number. Each lookup is O(1), so the overall time complexity becomes O(n) with O(n) extra space.

Is Check If N and Its Double Exist asked at Google/Amazon/Meta?

Problems involving hash sets, array scanning, and pair relationships appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the underlying pattern of using hash-based lookups to detect relationships between numbers is commonly tested.

What data structure is used in Check If N and Its Double Exist?

The primary data structure is a hash set (or hash table). It allows constant-time membership checks, which makes it possible to detect whether the required double or half value already appeared in the array.

What is the time complexity of Check If N and Its Double Exist?

The optimal solution runs in O(n) time using a hash set for constant‑time lookups. A sorting-based approach takes O(n log n) time due to the sort operation, while a naive brute force solution that checks every pair would take O(n^2).

Description Hints 3 Solution Video 14:57

1346. Check If N and Its Double Exist

Easy41.7% acceptance5 companies

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]

Example 1:

Input: arr = [10,2,5,3]
Output: true
Explanation: For i = 0 and j = 2, arr[i] == 10 == 2 * 5 == 2 * arr[j]

Example 2:

Input: arr = [3,1,7,11]
Output: false
Explanation: There is no i and j that satisfy the conditions.

Constraints:

2 <= arr.length <= 500
-10³ <= arr[i] <= 10³

Asked at 5 companies

Google Bloomberg Amazon Microsoft Meta

Topics

Hints open one at a time

Hint 1

Loop from i = 0 to arr.length, maintaining in a hashTable the array elements from [0, i - 1].

Hint 2

On each step of the loop check if we have seen the element 2 * arr[i] so far.

Hint 3

Also check if we have seen arr[i] / 2 in case arr[i] % 2 == 0.

14:57

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution