LeetCode Entry

2683. Neighboring Bitwise XOR

17.01.2025 medium 2025 kotlin rust

Can restore next-sibl-xored array?

2683. Neighboring Bitwise XOR medium blog post substack youtube deep-dive 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/867

Problem TLDR

Can restore next-sibl-xored array? #medium #xor

Intuition

Observe an example:


    // a b c
    // 1 1 0
    // a^b      a != b      a=1    b=1^1 = 0
    //   b^c    b != c      b=0    c=1^0 = 1
    //     c^a  c == a      c=1    a=0^1 = 1 correct

We can assume the initial value a and after all-xor operation compare if it is the same.

Approach

  • initial value can be 0 or 1

Complexity

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

  • Space complexity: \(O(1)\)

Code


    fun doesValidArrayExist(derived: IntArray) =
        derived.reduce(Int::xor) < 1



    pub fn does_valid_array_exist(derived: Vec<i32>) -> bool {
        derived.into_iter().reduce(|a, b| a ^ b).unwrap() < 1
    }



    bool doesValidArrayExist(vector<int>& derived) {
        int a = 1; for (int x: derived) a ^= x;
        return a;
    }