Method 1 – XOR Properties and Prefix XOR

Intuition

The encoded array is formed by XORing consecutive elements of a permutation of the first n positive integers. Since n is odd, we can use the properties of XOR to recover the original permutation. The key is that XOR-ing all numbers from 1 to n and all encoded values in a certain pattern allows us to deduce the first element, and then reconstruct the rest.

Approach

Let n = len(encoded) + 1.
Compute total as the XOR of all numbers from 1 to n (i.e., 1^2^...^n).
Compute odd as the XOR of all encoded elements at odd indices (i.e., encoded[1], encoded[3], ...).
The first element of perm is first = total ^ odd.
Reconstruct the rest of perm by iteratively XORing the previous value with the corresponding encoded value.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> decode(vector<int>& encoded) {\n        int n = encoded.size() + 1;\n        int total = 0;\n        for (int i = 1; i <= n; ++i) total ^= i;\n        int odd = 0;\n        for (int i = 1; i < n - 1; i += 2) odd ^= encoded[i];\n        vector<int> ans(n);\n        ans[0] = total ^ odd;\n        for (int i = 0; i < n - 1; ++i) {\n            ans[i + 1] = ans[i] ^ encoded[i];\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">decode</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> encoded</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> encoded.&#

Related Tags