31.10.2023
2433. Find The Original Array of Prefix Xor medium
blog post
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:
by using
mapIndexed
by in-place iteration
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 }
}