This is our solution and implementation to problem #1720: Decode XORed Array on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Decode XORed Array on LeetCode.
Problem Analysis
An xor operation on boolean variables compares the two booleans and returns true if their values are different and false otherwise. An xor operation on numbers comparies each nth bit, and if they are different, sets the output number's nth bit to 1, or 0 otherwise. Consider what happens if you repeat this process. The following is a truth table that has two boolean variables, the result of an xor operation, and the result of a 2nd xor operation between the original xor and the original 2nd variable:
A | B | A XOR B | (A XOR B) XOR B |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
Notice that the first and last columns are the same. A repeated XOR operation in this manner always yields the original variable input. The same applies to xor operations on numbers.
Implementation Strategy
Create a new list and add the first value in as given in the parameters. Then, loop over each encoded input and xor it with the last value (so far) in the new list and add it to the list.
Space and Time Complexity
The time complexity is O(n) as we iterate through each input once. The space complexity is O(n) since we create a new list to store the output.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.