Skip to content

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<int> decode(vector<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 `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<int> 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 `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[0] = 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 `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