LeetCode Entry

1346. Check If N and Its Double Exist

01.12.2024 easy 2024 kotlin rust

Any i != j && a[i] = 2 a[j]

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

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;
    }