# 01.12.2024 [1346. Check If N and Its Double Exist]

Any `i != j && a[i] = 2 * a[j]` #easy

01.12.2024

1346. Check If N and Its Double Exist easy blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/818

Problem TLDR

Any i != j && a[i] = 2 * a[j] #easy

Intuition

Several ways:

• brute-force O(n^2) and O(1) memory

• HashSet / bitset O(n) and O(n) memory

• sort & binary search O(nlogn) and O(logn) memory

• bucket sort O(n) and O(n) memory

Approach

• corner case is 0

Complexity

• Time complexity: $$O(n)$$

• Space complexity: $$O(n)$$

Code

    fun checkIfExist(arr: IntArray) = arr.groupBy { it }
        .run { keys.any { it != 0 && it * 2 in keys } 
            || get(0)?.size ?: 0 > 1 }

    pub fn check_if_exist(mut arr: Vec<i32>) -> bool {
        arr.sort_unstable(); (0..arr.len()).any(|i| { 
            i != arr.binary_search(&(2 * arr[i])).unwrap_or(i) })
    }

    bool checkIfExist(vector<int>& a) {
        int l = 1e3, f[2001] = {}; for (int x: a) ++f[x + l]; 
        for (int x = 500; --x;) 
            if (f[l + x] && f[l + x * 2] || f[l - x] && f[l - x * 2]) 
                return 1;
        return f[l] > 1 ? 1 : 0;
    }

    bool checkIfExist(vector<int>& a) {
        int l = 2000; bitset<4001>b;
        for (int x: a) if (b[x * 2 + l] || x % 2 < 1 && b[x / 2 + l]) 
            return 1; else b[x + l] = 1;
        return 0;
    }