Code Logo

Check If N and Its Double Exist

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given an array of integers, check if there exist two indices i and j such that i != j and either arr[i] = 2 * arr[j] or arr[j] = 2 * arr[i]. In other words, check if any element is exactly double another element.

A brute force double loop checks every pair in O(n²). Sorting the array and using binary search reduces this to O(n log n). For each element, search for its double using binary search. Because the array is sorted, binary search finds the target in O(log n) time.

An even simpler approach uses a hash set for O(n) time: iterate through the array, for each element check if its double or half (if even) exists in the set. If so, return true. Otherwise, add the element to the set and continue.

Edge cases include zeros (0*2=0, needs two zeros at different indices), negative numbers (-3*2=-6), and multiple duplicates. The hash set approach naturally handles these by checking for the double and half before inserting the current element.

The hash set approach is O(n) and works well for this problem. The key insight is checking both 2*n and n/2 (when n is even) against the set of previously seen elements. This ensures we find a pair regardless of which element appears first in the array.

Example Input & Output

Example 1
Input
[3,1,7,11]
Output
false
Explanation

No element is double another.

Example 2
Input
[0,0]
Output
true
Explanation

Two zeros: 0*2=0.

Example 3
Input
[-2,0,10,-4]
Output
true
Explanation

-2*2=-4 at indices 0 and 3.

Example 4
Input
[7,1,14,11]
Output
true
Explanation

2*7=14 at indices 0 and 2.

Example 5
Input
[10,2,5,3]
Output
true
Explanation

2*5=10, indices 0 and 2.

Algorithm Flow

Recommendation Algorithm Flow for Check If N and Its Double Exist
Recommendation Algorithm Flow for Check If N and Its Double Exist

Solution Approach

Hash set approach: for each n, check if 2*n or n/2 is already seen. If found, return true. Add n to the set.

function solution(arr) {
  var seen = {};
  for (var i = 0; i < arr.length; i++) {
    var n = arr[i];
    if (seen[n * 2] || (n % 2 === 0 && seen[n / 2])) return true;
    seen[n] = true;
  }
  return false;
}

Time O(n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public boolean solution(int[] arr) {
        Set<Integer> seen = new HashSet<>();
        for (int n : arr) {
            if (seen.contains(n * 2) || (n % 2 == 0 && seen.contains(n / 2))) return true;
            seen.add(n);
        }
        return false;
    }
}