aboutsummaryrefslogtreecommitdiff
path: root/decode_xored_permutation.py
diff options
context:
space:
mode:
Diffstat (limited to 'decode_xored_permutation.py')
-rw-r--r--decode_xored_permutation.py28
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]))