Skip to main content

1346. Check If N and Its Double Exist

easy

Given an array, determine whether there exist two distinct indices i and j with arr[i] == 2 * arr[j]. The double-of-a-number probe — handle zero carefully.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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, and arr[i] == 2 * arr[j].

Constraints

  • 2 <= arr.length <= 500
  • -10^3 <= arr[i] <= 10^3

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force tries every pair (i, j) — O(n^2). For n = 500 that's 250k, comfortable.

Hint 2

Hash-set: store seen values; for each new x check if 2*x or x/2 (if even) is already in the set.

Hint 3

Zero is the gotcha — two distinct zeros satisfy the condition because arr[i] == 0 == 2 * 0 == 2 * arr[j]. Handle 'count of zeros >= 2' separately.

Solution approach

Reveal approach

Single-pass with a hash set. Walk the array. For each value x, check whether 2*x is already in the seen set, or whether x is even and x/2 is already in the seen set — if yes, return true. Then add x to the seen set. The 'double of a previously seen number' and 'half of a previously seen number' covers both directions. For x = 0 specifically, both 2*x and x/2 equal x, so the condition becomes 'have we seen 0 before?' — which is exactly what the seen set will tell us. O(n) time, O(n) space. Brute force is also acceptable given the n <= 500 bound.

Complexity

Time
O(n)
Space
O(n)

Related patterns

  • hash-map
  • bit-manipulation

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon

Practice these live with InterviewChamp.AI

Drill Check If N and Its Double Exist and Bit Manipulation problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →