LeetCode Entry

2433. Find The Original Array of Prefix Xor

31.10.2023 medium 2023 kotlin

Reverse xor operation

2433. Find The Original Array of Prefix Xor medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/387

Problem TLDR

Reverse xor operation

Intuition

Let’s observe how xor works:

    // 010 2
    // 101 5
    // 111 7
    // 5 xor 7 = 2
    // 101 xor 111 = 010
    // 5 xor 2 = 101 xor 010 = 111

We can reverse the xor operation by applying it again: a ^ b = c, then a ^ c = b

Approach

There are several ways to write this:

  1. by using mapIndexed
  2. by in-place iteration
  3. by creating a new array

Let’s use Kotlin’s array constructor lambda and getOrElse.

Complexity

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

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

Code


    fun findArray(pref: IntArray) = IntArray(pref.size) {
      pref[it] xor pref.getOrElse(it - 1) { 0 }
    }