Is that true that result of decoding XORed permutation will always be unique?

Question

I'm struggling with the LeetCode task: Decode XORed Permutation

There is an integer array perm that is a permutation of the first n positive integers, where n is always odd.

It was encoded into another integer array encoded of length n - 1, such that encoded[i] = perm[i] XOR perm[i + 1]. For example, if perm = [1,3,2], then encoded = [2,1].

Given the encoded array, return the original array perm. It is guaranteed that the answer exists and is unique.

I wanted to solve it this way:

1. Make XOR of all elements of encoded array. Let's name it X
2. Make XOR of elements of encoded array that are at even positions (so I remove all elements except the first element in resulting permutation array). Let's name it Y
3. I do X xor Y and it's my first element in permutation array.

If I know the first element, I can easily solve whole problem. That's the code:

std::vector<int> decode(std::vector<int> encoded) {
    int xor_of_encoded = 0;
    int xor_without_known_elements = 0;
    for (int i = 0; i < encoded.size(); i++) {
        xor_of_encoded ^= encoded[i];
        if (i % 2 == 1)
            xor_without_known_elements ^= encoded[i];
    }

    std::vector<int> decoded(encoded.size() + 1);
    decoded[0] = xor_of_encoded ^ xor_without_known_elements;

    for (int i = 1; i <= encoded.size(); i++) {
        decoded[i] = (encoded[i - 1] ^ decoded[i - 1]);
    }

    return decoded;
}

A visual representation of how it works:

   6   5   4   6         <-- encoded
   |   |   |   |
   Ʌ   Ʌ   Ʌ   Ʌ
  / \ / \ / \ / \
 |   V   V   V   |
 |   |   |   |   |
 2   4   1   5   3       <-- result

When I submit my solution, it passes for second test case: [6,5,4,6]. It fails for the [3,1] and for [12,6,11,10,5,3,4,6] and probably for others but I didn't have a chance to test it for the rest of cases. The problem is that the result produced by my code meets the assumptions of the task.

When I manually XORed results of above code (decoded[i] xor decoded[i+1], so that's how the encoded array is created as mentioned in task) , I was able to recreate the encoded array.

So I'm confused about this problem. Do I have much luck or missed something, or the result is not unique?

Answer 1

You need to find the missing first number.

Of all the numbers from 1 to n, how many have bit 0 set?

Lets say you assume the missing number is 0, decode the rest, and find that there are a results with bit 0 set, and b results with bit 0 not set.

If you instead set bit 0 of the assumed first number, then there would be b results with bit 0 set, and a results with bit 0 not set.

Since a+b = n, and n is odd, we know that a != b, so set bit 0 of the missing first number to whatever value produces the correct counts.

Do the same for the remaining bits, and you have the whole first number, and can easily decode the rest.