---
# System prepended metadata

title: 1734. Decode XORed Permutation
tags: [Leetcode, Bit Manipulation, XOR, Medium]

---

# 1734. Decode XORed Permutation
###### tags: `Leetcode` `Medium` `Bit Manipulation` `XOR`
Link: https://leetcode.com/problems/decode-xored-permutation/
## 思路
如果间隔着取encode里面的元素再XOR起来，就得到```nohead = nums[1]^numx[2]^...^nums[n-1]```, (这就是为什么n必须是奇数)只缺少了nums[0]而已.再加上全局的XOR Sum其实是已知的（因为题目说的是1到n的permutation）所以如果我们把nohead与XORSum再亦或一下，就得到了nums[0]。于是nums[1]就可以从encode[0]^nums[0]得到，其余的nums[i]也就迎刃而解。
## Code
```java=
class Solution {
    public int[] decode(int[] encoded) {
        int sum = 0;
        for(int i=1; i<=encoded.length+1; i++){
            sum^=i;
        }
        
        int nohead = 0;
        for(int i=1; i<encoded.length; i+=2){
            nohead ^= encoded[i];
        }
        
        int head = nohead^sum;
        int[] ans = new int[encoded.length+1];
        ans[0] = head;
        for(int i=1; i<ans.length; i++){
            ans[i] = ans[i-1]^encoded[i-1];
        }
        return ans;
    }
}
```