We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find The Original Array of Prefix Xor

Number: 2519

Difficulty: Medium

Paid? No

Companies: Amazon, IBM, Nvidia, Morgan Stanley

Problem Description

Given an integer array pref where for every index i, pref[i] is defined as the XOR of all elements from arr[0] to arr[i] (i.e. pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]), recover and return the original array arr.

Key Insights

  • The first element of arr is the same as pref[0].
  • For i > 0, arr[i] can be obtained by XOR-ing pref[i] with pref[i-1] because XOR is its own inverse.
  • The problem guarantees that the solution is unique.
  • The XOR operation has properties that help in inverting prefix computations.

Space and Time Complexity

Time Complexity: O(n) - We traverse the array once. Space Complexity: O(n) - We use an extra array to store the result.

Solution

The key idea is to use the property of XOR where a ^ b ^ b = a. Given that pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i], we can deduce that for i > 0, arr[i] = pref[i-1] ^ pref[i]. We initiate arr[0] with pref[0] and then for each index i from 1 to n-1, we compute arr[i] using the XOR of pref[i-1] and pref[i]. This method is efficient and runs in linear time while using linear space.

Code Solutions

# Function to find the original array from pref array
def findArray(pref):
    # Initialize the result array with the same length as pref
    n = len(pref)
    arr = [0] * n
    # The first element is the same as in pref
    arr[0] = pref[0]
    # For the rest of the elements, apply the relation: arr[i] = pref[i-1] ^ pref[i]
    for i in range(1, n):
        arr[i] = pref[i - 1] ^ pref[i]
    return arr

# Example usage:
# input_pref = [5, 2, 0, 3, 1]
# print(findArray(input_pref))  # Output: [5, 7, 2, 3, 2]
← Back to All Questions