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

Examples

Example 1

1
2
3

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

1
2
3

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^3 <= arr[i] <= 10^3

Solution

Method 1 – Hash Set Lookup

Intuition

We want to quickly check if for any number in the array, its double or half (if even) also exists elsewhere in the array. Using a hash set allows for fast lookups.

Reasoning

By storing all numbers in a set, we can check for each number if its double or, if the number is even, its half exists in the set (excluding itself for the half case). This covers all possible pairs efficiently.

Approach

  1. Create a set of all numbers in the array.
  2. For each number x in the array:
    • Check if 2 * x exists in the set and 2 * x != x or if x is even and x // 2 exists in the set and x // 2 != x.
    • If such a pair is found, return true.
  3. If no such pair is found, return false.

Edge cases:

  • Duplicates: If x is zero, need at least two zeros for a valid pair.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    bool checkIfExist(vector<int>& arr) {
        unordered_set<int> s(arr.begin(), arr.end());
        int zeroCount = count(arr.begin(), arr.end(), 0);
        if (zeroCount > 1) return true;
        for (int x : arr) {
            if (x != 0 && s.count(2 * x)) return true;
            if (x % 2 == 0 && x != 0 && s.count(x / 2)) return true;
        }
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func checkIfExist(arr []int) bool {
    s := make(map[int]struct{})
    zeroCount := 0
    for _, x := range arr {
        s[x] = struct{}{}
        if x == 0 {
            zeroCount++
        }
    }
    if zeroCount > 1 {
        return true
    }
    for _, x := range arr {
        if x != 0 {
            if _, ok := s[2*x]; ok {
                return true
            }
            if x%2 == 0 {
                if _, ok := s[x/2]; ok {
                    return true
                }
            }
        }
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public boolean checkIfExist(int[] arr) {
        Set<Integer> s = new HashSet<>();
        int zeroCount = 0;
        for (int x : arr) {
            s.add(x);
            if (x == 0) zeroCount++;
        }
        if (zeroCount > 1) return true;
        for (int x : arr) {
            if (x != 0 && s.contains(2 * x)) return true;
            if (x % 2 == 0 && x != 0 && s.contains(x / 2)) return true;
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun checkIfExist(arr: IntArray): Boolean {
        val s = arr.toSet()
        val zeroCount = arr.count { it == 0 }
        if (zeroCount > 1) return true
        for (x in arr) {
            if (x != 0 && 2 * x in s) return true
            if (x % 2 == 0 && x != 0 && x / 2 in s) return true
        }
        return false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def check_if_exist(self, arr: list[int]) -> bool:
        s = set(arr)
        zero_count = arr.count(0)
        if zero_count > 1:
            return True
        for x in arr:
            if x != 0 and 2 * x in s:
                return True
            if x % 2 == 0 and x != 0 and x // 2 in s:
                return True
        return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn check_if_exist(arr: Vec<i32>) -> bool {
        let mut s: std::collections::HashSet<i32> = arr.iter().cloned().collect();
        let zero_count = arr.iter().filter(|&&x| x == 0).count();
        if zero_count > 1 {
            return true;
        }
        for &x in &arr {
            if x != 0 && s.contains(&(2 * x)) {
                return true;
            }
            if x % 2 == 0 && x != 0 && s.contains(&(x / 2)) {
                return true;
            }
        }
        false
    }
}

Complexity

  • ⏰ Time complexity: O(n), as we scan the array a constant number of times and set lookups are O(1) on average.
  • 🧺 Space complexity: O(n), as we store all elements in a set for fast lookup.