Decode XORed Array Solution in C++

Problem Description

Ah, the classic “Decode XORed Array” problem! It’s like trying to figure out what your friend meant when they sent you a cryptic text message after a night out. You know there’s a hidden meaning, but good luck deciphering it!

In this problem, you are given an encoded array and a starting integer, first. The encoded array is created by taking the XOR of consecutive elements from the original array. Your task is to decode this array and retrieve the original array.

Imagine you’re at a party, and someone keeps passing you notes that are just a series of XOR operations. You need to figure out what they were trying to say before the snacks run out!

Code Solution


class Solution {
 public:
  vector decode(vector& encoded, int first) {
    vector ans(encoded.size() + 1);
    ans[0] = first;

    for (int i = 0; i < encoded.size(); ++i)
      ans[i + 1] = ans[i] ^ encoded[i];

    return ans;
  }
};

Approach

The approach here is quite straightforward. We initialize an answer array with the first element set to the given first integer. Then, we iterate through the encoded array, using the XOR operation to decode each subsequent element. The beauty of XOR is that it allows us to reverse the encoding process seamlessly.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the encoded array. We traverse the array once.
Space Complexity	O(n), as we are storing the decoded array.

Real-World Example

Think of it like this: You’re trying to piece together a jigsaw puzzle, but someone has mixed up the pieces. The encoded array is like the jumbled pieces, and your job is to put them back together using the first piece as a reference. Each XOR operation helps you find the right piece to fit next!