diff options
Diffstat (limited to 'decode_xor_array.c')
-rw-r--r-- | decode_xor_array.c | 35 |
1 files changed, 35 insertions, 0 deletions
diff --git a/decode_xor_array.c b/decode_xor_array.c new file mode 100644 index 0000000..d709fbf --- /dev/null +++ b/decode_xor_array.c @@ -0,0 +1,35 @@ +// 720. Decode XORed Array +#include <stdio.h> +#include <stdlib.h> + +/* + * there is a hidden integer array 'arr' that consists of 'n' non-negative + * integers. it was encoded into another integer array 'encoded' of length 'n - + * 1' such that 'encoded[i] = arr[i] ^ arr[i + 1]'. for example, if 'arr = + * [1,0,2,1]', then 'encoded = [1,2,3]'. you are given the 'encoded' array. you + * are also given an integer 'first', that is the first element of 'arr'. ie. of + * 'arr[0]'. return the original array 'arr'. it can be proved that the answer + * exists and is unique. + */ + +int *decode(int *encoded, int encoded_size, int first, int *return_size) { + *return_size = encoded_size + 1; + int *arr = (int *)malloc(*return_size * sizeof(int)); + arr[0] = first; + for (int i = 0; i < encoded_size; i++) + arr[i + 1] = arr[i] ^ encoded[i]; + return arr; +} + +int main() { + int e1[] = {1, 2, 3}, es1 = 3, f1 = 1, rs1[] = {}; + int e2[] = {6, 2, 7, 3}, es2 = 4, f2 = 4, rs2[] = {}; + int *d1 = decode(e1, es1, f1, rs1); + int *d2 = decode(e2, es2, f2, rs2); + for (int i = 0; i < es1 + 1; i++) + printf("%d ", d1[i]); // expect: 1 0 2 1 + printf("\n"); + for (int i = 0; i < es2 + 1; i++) + printf("%d ", d2[i]); // expect: 4 2 0 7 4 + printf("\n"); +} |