aboutsummaryrefslogtreecommitdiff
path: root/decode_xored_permutation.c
blob: 59f9a588b0a938dfa6d3a91dc4e39d8bde7ffa62 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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);
}