Problem Description

You are given an integer array pref of size n. The goal is to find and return the array arr of size n that satisfies the following condition:

pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]

Here, ^ denotes the bitwise-xor operation.

Example

Input

pref = [5, 2, 0, 3, 1]

Output

[5, 7, 2, 3, 2]

Explanation

From the array [5, 7, 2, 3, 2], we have the following:

pref[0] = 5 pref[1] = 5 ^ 7 = 2 pref[2] = 5 ^ 7 ^ 2 = 0 pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3 pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1

Implementation Details

We provide a C++ solution using a class Solution with a method findArray.

class Solution {
public:
    vector<int> findArray(vector<int>& pref) {
        int n = pref.size();
        vector<int> arr(n);

        arr[0] = pref[0]; // The first element of arr is equal to the first element of pref

        // Iterate through the pref array to find the elements of arr
        for (int i = 1; i < n; i++) {
            arr[i] = pref[i] ^ pref[i - 1];
        }

        return arr;
    }
};

Explanation

  1. Initialize n with the size of the input array pref.
  2. Create a vector arr to store the resulting array.
  3. Set the first element of arr to be equal to the first element of pref.
  4. Iterate through the pref array starting from index 1.
  5. At each step, calculate arr[i] using the XOR operation with the current element pref[i] and the previous element pref[i - 1].
  6. Return the resulting arr.

This solution leverages the property of XOR operation to find the array arr that satisfies the given condition.

Feel free to include any additional information or context that might be relevant to your specific use case.