Code Logo

Check If N and Its Double Exist

Published at24 Jul 2026
Created by
Easy 1 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

Solution Approach

Check if an array contains a pair where one element is double another. Use a hash set to store numbers as you iterate. For each element n, check if either 2*n or n/2 (when n is even) exists in the set. If found, return true. Otherwise, add n to the set. This handles both directions: a later number could be double an earlier one, or an earlier number could be half of the current one.

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

Checking both arr[i]*2 and arr[i]/2 covers both cases: the double existing ahead or behind. The modulo check ensures we only look for n/2 when n is even, avoiding false positives from integer division of odd numbers.

Time complexity is O(n), space complexity is 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;
    }
}