# 1734. Decode XORed Permutation    • Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public: vector decode(vector& encoded) { // Our goal is to find the value of a1, which will allow us to decode a2, // a3, ..., an. This can be achieved by performing XOR operation between // each element in the encoded and a1. // // E.g. n = 3, perm = [a1, a2, a3] is a permutation of [1, 2, 3] // encoded = [a1^a2, a2^a3] // accumulatedEncoded = [a1^a2, a1^a3] // a1 = (a1^a2)^(a1^a3)^(a1^a2^a3) // a2 = a1^(a1^a2) // a3 = a2^(a2^a3) const int n = encoded.size() + 1; int nXors = 0; for (int i = 1; i <= n; i++) nXors ^= i; // Instead of constructing the array, we can track of the running XOR value // of accumulatedEncoded. int runningXors = 0; int xors = 0; // xors(accumulatedEncoded) for (const int encode : encoded) { runningXors ^= encode; xors ^= runningXors; } vector ans{xors ^ nXors}; for (const int encode : encoded) ans.push_back(ans.back() ^ encode); return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public int[] decode(int[] encoded) { // Our goal is to find the value of a1, which will allow us to decode a2, // a3, ..., an. This can be achieved by performing XOR operation between // each element in the encoded and a1. // // E.g. n = 3, perm = [a1, a2, a3] is a permutation of [1, 2, 3] // encoded = [a1^a2, a2^a3] // accumulatedEncoded = [a1^a2, a1^a3] // a1 = (a1^a2)^(a1^a3)^(a1^a2^a3) // a2 = a1^(a1^a2) // a3 = a2^(a2^a3) final int n = encoded.length + 1; int nXors = 0; for (int i = 1; i <= n; i++) nXors ^= i; // Instead of constructing the array, we can track of the running XOR value // of accumulatedEncoded. int runningXors = 0; int xors = 0; // xors(accumulatedEncoded) for (final int encode : encoded) { runningXors ^= encode; xors ^= runningXors; } int[] ans = new int[encoded.length + 1]; ans = xors ^ nXors; for (int i = 0; i < encoded.length; i++) ans[i + 1] = ans[i] ^ encoded[i]; return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution: def decode(self, encoded: List[int]) -> List[int]: # Our goal is to find the value of a1, which will allow us to decode a2, a3, # ..., an. This can be achieved by performing XOR operation between each # element in the encoded and a1. # # E.g. n = 3, perm = [a1, a2, a3] is a permutation of [1, 2, 3]. # encoded = [a1^a2, a2^a3] # accumulatedEncoded = [a1^a2, a1^a3] # a1 = (a1^a2)^(a1^a3)^(a1^a2^a3) # a2 = a1^(a1^a2) # a3 = a2^(a2^a3) n = len(encoded) + 1 nXors = functools.reduce(operator.xor, [i for i in range(1, n + 1)]) # Instead of constructing the array, we can track of the running XOR value # of accumulatedEncoded. xors = 0 # xors(accumulatedEncoded) for encode in encoded: runningXors ^= encode xors ^= runningXors ans = [xors ^ nXors] for encode in encoded: ans.append(ans[-1] ^ encode) return ans