diff options
Diffstat (limited to 'decode_xored_permutation.py')
-rw-r--r-- | decode_xored_permutation.py | 28 |
1 files changed, 28 insertions, 0 deletions
diff --git a/decode_xored_permutation.py b/decode_xored_permutation.py new file mode 100644 index 0000000..f84499d --- /dev/null +++ b/decode_xored_permutation.py @@ -0,0 +1,28 @@ +# 1734. Decode XORed Permutation +from operator import ixor +from functools import reduce +from itertools import accumulate + +""" +there is a positive 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] ^ +perm[i + 1]'. given the 'encoded' array, return the original array 'perm'. it +is guaranteed that the answer exists and is unique +""" + + +class Solution(object): + def decode(self, encoded): + """ + :type encoded: List[int] + :rtype: List[int] + """ + first = reduce(ixor, encoded[::-2] + list(range(len(encoded) + 2))) + return list(accumulate([first] + encoded, ixor)) + + +if __name__ == "__main__": + obj = Solution() + print(obj.decode(encoded=[3, 1])) + print(obj.decode(encoded=[6, 5, 4, 6])) |