LeetCode - Find The Original Array of Prefix XOR

Problem statement

You are given an integer array pref of size n. Find and return the array arr of size n that satisfies:

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

Note that ^ denotes the bitwise-xor operation.

It can be proven that the answer is unique.

Problem statement taken from: https://leetcode.com/problems/find-the-original-array-of-prefix-xor

Example 1:

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.

Example 2:

Input: pref = [13]
Output: [13]
Explanation: We have pref[0] = arr[0] = 13.

Constraints:

- 1 <= pref.length <= 10^5
- 0 <= pref[i] <= 10^6

Explanation

For an XOR operator, we have the following set of operations to be true.

a ^ b = c
a ^ c = b

Eg

5 ^ 7 = 2
5 ^ 2 = 7

We use this approach to get back our original array.

Let's check the algorithm first.

- set n = pref.size()

- if n == 0 || n == 1
  - return pref

- loop for i = n - 1; i >= 1; i--
  - pref[i] = pref[i] ^ pref[i - 1]

- return pref

The time complexity of the above approach is O(n), and the space complexity is O(1).

Let's check our algorithm in C++, Golang, and JavaScript.

C++ solution

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

        if(n == 0 || n == 1) {
            return pref;
        }

        for(int i = n - 1; i >= 1; i--) {
            pref[i] ^= pref[i - 1];
        }

        return pref;
    }
};

Golang solution

func findArray(pref []int) []int {
    n := len(pref)

    if n == 0 || n == 1 {
        return pref
    }

    for i := n - 1; i >= 1; i-- {
        pref[i] ^= pref[i - 1]
    }

    return pref
}

JavaScript solution

var findArray = function(pref) {
    let n = pref.length;

    if(n === 0 || n === 1) {
        return pref;
    }

    for(let i = n - 1; i >= 1; i--) {
        pref[i] ^= pref[i - 1];
    }

    return pref;
};

Dry Run

Let's dry-run our algorithm for Example 1.

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

Step 1: n = pref.size()
          = 5

Step 2: if n == 0 || n == 1
           5 == 0 || 5 == 1
           false

Step 3: loop for i = n - 1; i >= 1; i--
          i = 5 - 1 = 4
          4 >= 1
          true

          pref[i] = pref[i] ^ pref[i - 1]
                  = pref[4] ^ pref[3]
                  = 1 ^ 3
                  = 2

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

          i--
          i = 3

Step 4: loop for i >= 1
          3 >= 1
          true

          pref[i] = pref[i] ^ pref[i - 1]
                  = pref[3] ^ pref[2]
                  = 3 ^ 0
                  = 3

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

          i--
          i = 2

Step 5: loop for i >= 1
          2 >= 1
          true

          pref[i] = pref[i] ^ pref[i - 1]
                  = pref[2] ^ pref[1]
                  = 0 ^ 2
                  = 2

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

          i--
          i = 1

Step 6: loop for i >= 1
          1 >= 1
          true

          pref[i] = pref[i] ^ pref[i - 1]
                  = pref[1] ^ pref[0]
                  = 2 ^ 5
                  = 7

          pref = [5, 7, 2, 3, 2]

          i--
          i = 0

Step 7: loop for i >= 1
          0 >= 1
          false

Step 8: return pref

We return the answer as [5, 7, 2, 3, 2].