In this guide, you will get 1720. Decode XORed Array LeetCode Solution with the best time and space complexity. The solution to Decode XORed Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
There is a hidden integer array arr that consists of n non-negative integers.
It was encoded into another integer array encoded of length n – 1, such that encoded[i] = arr[i] XOR arr[i + 1]. For example, if arr = [1,0,2,1], then encoded = [1,2,3].
You are given the encoded array. You are also given an integer first, that is the first element of arr, i.e. arr[0].
Return the original array arr. It can be proved that the answer exists and is unique.
Example 1:
Input: encoded = [1,2,3], first = 1
Output: [1,0,2,1]
Explanation: If arr = [1,0,2,1], then first = 1 and encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
Example 2:
Input: encoded = [6,2,7,3], first = 4
Output: [4,2,0,7,4]
Constraints:
2 <= n <= 104
encoded.length == n – 1
0 <= encoded[i] <= 105
0 <= first <= 105
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
1720. Decode XORed Array LeetCode Solution in C++
class Solution {
public:
vector<int> decode(vector<int>& encoded, int first) {
vector<int> ans(encoded.size() + 1);
ans[0] = first;
for (int i = 0; i < encoded.size(); ++i)
ans[i + 1] = ans[i] ^ encoded[i];
return ans;
}
}; /* code provided by PROGIEZ */
1720. Decode XORed Array LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
1720. Decode XORed Array LeetCode Solution in Python
class Solution:
def decode(self, encoded: list[int], first: int) -> list[int]:
ans = [first]
for e in encoded:
ans.append(e ^ ans[-1])
return ans # code by PROGIEZ
