Check If N and Its Double Exist

easy hash set

Problem

You are given an integer array arr (2 to 500 elements, each value between −1000 and 1000). Decide whether it contains two different indices i and j such that arr[i] = 2 × arr[j] — in other words, some element is exactly the double of another element. Return true if such a pair exists, false otherwise.

Inputarr = [10, 2, 5, 3]

Outputtrue

5 sits at index 2 and its double 10 sits at index 0, so a valid pair of indices exists.

arr (comma-separated integers)

def check_if_exist(arr):
    seen = set()
    for x in arr:
        if 2 * x in seen or (x % 2 == 0 and x // 2 in seen):
            return True
        seen.add(x)
    return False

function checkIfExist(arr) {
  const seen = new Set();
  for (const x of arr) {
    if (seen.has(2 * x) || (x % 2 === 0 && seen.has(x / 2))) {
      return true;
    }
    seen.add(x);
  }
  return false;
}

boolean checkIfExist(int[] arr) {
    Set<Integer> seen = new HashSet<>();
    for (int x : arr) {
        if (seen.contains(2 * x) || (x % 2 == 0 && seen.contains(x / 2))) {
            return true;
        }
        seen.add(x);
    }
    return false;
}

bool checkIfExist(vector<int>& arr) {
    unordered_set<int> seen;
    for (int x : arr) {
        if (seen.count(2 * x) || (x % 2 == 0 && seen.count(x / 2))) {
            return true;
        }
        seen.insert(x);
    }
    return false;
}

Explanation

The brute force compares every pair of indices looking for arr[i] = 2 · arr[j], which costs O(n²). The hash-set trick turns this into a single pass: a set seen holds every value met so far, and for each new value x we replace a rescan of the whole prefix with two O(1) membership questions.

Why two questions? If x pairs with some earlier element y, there are only two possibilities: either y = 2x (the earlier element is the double) or y = x/2 (the earlier element is the half). So we look up 2 * x, and — only when x is even — x / 2. An odd number cannot be the double of any integer, so the half check is safely skipped for odd x.

Walking the default example arr = [10, 2, 5, 3]: for x = 10 neither 20 nor 5 is in the empty set, so 10 is inserted. For x = 2 neither 4 nor 1 is present, so 2 is inserted. For x = 5 we ask whether 10 is in seen — it is, so the function returns true immediately without ever looking at 3.

Zero deserves a note: the double of 0 is 0 itself, so a single 0 must not match itself — only two zeros form a valid pair. The order of operations protects us automatically, because we query the set before inserting the current element; a lone 0 finds nothing, and a second 0 finds the first.

Each element triggers at most two hash lookups and one insertion, all expected O(1), so the total time is O(n). The set stores at most n distinct values, so the extra space is O(n). Checking before inserting also guarantees the matched partner always lives at a strictly earlier — hence different — index.

Time: O(n) Space: O(n)