aboutsummaryrefslogtreecommitdiff
path: root/beautiful_array.c
blob: d38406697b106a1e68f1eee77d0d11c2eb968f6f (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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 932. Beautiful Array
#include "leetcode.h"

/*
 * an array 'nums' of length 'n' is beautiful if 'nums' is a permutation of the
 * integers in the range '[1, n]', and for every '0 <= i < j < n', there is no
 * index 'k' with 'i < k < j' where '2 * nums[k] == nums[i] + nums[j]'. given
 * the integer 'n', return any beautiful array 'nums' of length 'n'. there will
 * be at least one valid answer for the given 'n'.
 */

int *build_arr(int n, int **ans) {
  if (ans[n])
    return ans[n];
  int *res = (int *)malloc(n * sizeof(int));
  if (n == 1)
    res[0] = 1;
  else {
    int j = 0;
    int *odds = build_arr((n + 1) / 2, ans);
    for (int k = 0; k < (n + 1) / 2; k++)
      res[k] = 2 * odds[k] - 1;
    int *evens = build_arr(n / 2, ans);
    for (int k = 0; k < n / 2; k++)
      res[((n + 1) / 2) + k] = 2 * evens[k];
  }
  ans[n] = res;
  return res;
}

int *beautifulArray(int n, int *returnSize) {
  int *ans = (int *)malloc(n * sizeof(int));
  *returnSize = n;
  if (n == 1) {
    ans[0] = 1;
    return ans;
  }
  if (n == 2) {
    ans[0] = 1;
    ans[1] = 2;
    return ans;
  }
  int **res = (int **)malloc((n + 1) * sizeof(int *));
  for (int i = 0; i < n + 1; i++)
    res[i] = NULL;
  ans = build_arr(n, res);
  *returnSize = n;
  for (int i = 0; i < n; i++)
    free(res[i]);
  free(res);
  return ans;
}

int main() {
  int rs1, *ba1 = beautifulArray(4, &rs1);
  int rs2, *ba2 = beautifulArray(5, &rs2);
  for (int i = 0; i < rs1; i++)
    printf("%d ", ba1[i]); // expect: 2 1 4 3
  printf("\n");
  for (int i = 0; i < rs2; i++)
    printf("%d ", ba2[i]); // expect: 3 1 2 5 4
  printf("\n");
  free(ba1), free(ba2);
}