problemeasyalgorithmsleetcode-1346leetcode 1346leetcode1346

Check If N and Its Double Exist

EasyUpdated: Jul 7, 2025
Practice on:
LeetCode

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

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.

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

C++
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;
    }
};
Go
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
}
Java
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;
    }
}
Kotlin
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
    }
}
Python
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
Rust
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.

Comments