Find The Original Array of Prefix Xor Solution in Python

Language Links

Code Solution


class Solution:
    def findArray(self, pref: list[int]) -> list[int]:
        ans = [0] * len(pref)

        ans[0] = pref[0]
        for i in range(1, len(ans)):
            ans[i] = pref[i] ^ pref[i - 1]

        return ans

Problem Description

So, you think you can just take a list of numbers and magically figure out the original array from it? Welcome to the world of Prefix Xor! The problem is simple yet perplexing, like trying to find your keys in a messy room. Given an array pref, which is the prefix XOR of some original array arr, your task is to find that original array.

Imagine you have a secret recipe for a cake, but all you have is the final cake. You need to figure out the ingredients (the original array) just by looking at the cake (the prefix XOR). Sounds fun, right?

Approach

The approach is straightforward. The first element of the original array is the same as the first element of the prefix array. For the subsequent elements, you can use the property of XOR: a ^ b = c implies a = b ^ c. Thus, each element in the original array can be derived from the prefix array using the XOR operation.

Time and Space Complexity

Time Complexity: O(n), where n is the length of the prefix array. We traverse the array once.
Space Complexity: O(n), as we are using an additional array to store the result.

Real-World Example

Think of it like a game of telephone. You whisper a message to your friend, and they pass it along. By the time it reaches the last person, the message has changed. The prefix XOR is like the final message, and your job is to figure out what the original message was.