diff options
author | Jack Sangdahl <[email protected]> | 2024-12-26 21:37:29 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-26 21:37:29 -0700 |
commit | a52ccc2d81430bae1862eebf40055815e1ff1c73 (patch) | |
tree | 48ff24a6393f7eb3a99f6706ab39586d3ea4b159 | |
parent | 96f4b139b722ffd32f1130499733f39000eabab4 (diff) | |
download | leetcode-a52ccc2d81430bae1862eebf40055815e1ff1c73.tar.gz leetcode-a52ccc2d81430bae1862eebf40055815e1ff1c73.zip |
1734. deocde xored permutation
-rw-r--r-- | decode_xored_permutation.c | 37 | ||||
-rw-r--r-- | decode_xored_permutation.py | 28 |
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])) |