aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-26 21:37:29 -0700
committerJack Sangdahl <[email protected]>2024-12-26 21:37:29 -0700
commita52ccc2d81430bae1862eebf40055815e1ff1c73 (patch)
tree48ff24a6393f7eb3a99f6706ab39586d3ea4b159
parent96f4b139b722ffd32f1130499733f39000eabab4 (diff)
downloadleetcode-a52ccc2d81430bae1862eebf40055815e1ff1c73.tar.gz
leetcode-a52ccc2d81430bae1862eebf40055815e1ff1c73.zip
1734. deocde xored permutation
-rw-r--r--decode_xored_permutation.c37
-rw-r--r--decode_xored_permutation.py28
2 files changed, 65 insertions, 0 deletions
diff --git a/decode_xored_permutation.c b/decode_xored_permutation.c
new file mode 100644
index 0000000..59f9a58
--- /dev/null
+++ b/decode_xored_permutation.c
@@ -0,0 +1,37 @@
+// 1734. Decode XORed Permutation
+#include "leetcode.h"
+
+/*
+ * 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
+ */
+
+int *decode(int *encoded, int encodedSize, int *returnSize) {
+ *returnSize = encodedSize + 1;
+ int *ans = (int *)malloc(*returnSize * sizeof(int)), all = 0;
+ for (int i = 0; i < *returnSize; i++)
+ all ^= i + 1;
+ int first = all;
+ for (int i = 1; i < encodedSize; i += 2)
+ first ^= encoded[i];
+ ans[0] = first;
+ for (int i = 0; i < encodedSize; i++)
+ ans[i + 1] = ans[i] ^ encoded[i];
+ return ans;
+}
+
+int main() {
+ int e1[] = {3, 1}, e2[] = {6, 5, 4, 6}, rs1, rs2;
+ int *d1 = decode(e1, ARRAY_SIZE(e1), &rs1);
+ int *d2 = decode(e2, ARRAY_SIZE(e2), &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", d1[i]); // expect: 1 2 3
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", d2[i]); // expect: 2 4 1 5 3
+ printf("\n");
+ free(d1), free(d2);
+}
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]))