Decode XORed Array Solution in Java

Explore Solutions in Other Languages

Problem Description

So, you’ve stumbled upon the Decode XORed Array problem on LeetCode, huh? Well, let me break it down for you. Imagine you’re at a party, and someone hands you a mysterious box filled with numbers. You know the first number, but the rest are all jumbled up in a way that only a secret code can decode them. Sounds like a spy movie, right?

In this problem, you’re given an array called encoded, which is a series of numbers that have been XORed with the original array (let’s call it arr). You also have the first number of the original array. Your mission, should you choose to accept it, is to decode the rest of the numbers in arr.

Code Solution

class Solution {
  public int[] decode(int[] encoded, int first) {
    int[] ans = new int[encoded.length + 1];
    ans[0] = first;

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

    return ans;
  }
}

Approach

The approach here is as simple as pie (or maybe a slice of cake, if you prefer). You start with the first number of the original array and then use the XOR operation to decode the rest of the numbers. The XOR operation is like a magical key that helps you unlock the secrets of the encoded array. For each number in the encoded array, you XOR it with the last decoded number to get the next number in the original array. Voilà! You’ve decoded the array!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the length of the `encoded` array.
Space Complexity	O(n), because you’re creating a new array to store the decoded numbers.

Real-World Example

Let’s say you’re trying to decode a secret recipe for the world’s best chocolate cake. You know the first ingredient is flour (let’s say it’s represented by the number 5). The encoded array might represent the amounts of sugar, cocoa, and eggs, but they’re all jumbled up. By using the XOR operation, you can decode the amounts of each ingredient and finally bake that cake!