aboutsummaryrefslogtreecommitdiff
path: root/beautiful_array.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-10 23:14:36 -0600
committerJack Sangdahl <[email protected]>2025-07-10 23:14:36 -0600
commit19c811f19b9732c8166e632535d1262093ae5006 (patch)
tree3d8e7a9e6c783188561ec961699a50b290296664 /beautiful_array.c
parentb56ca2e2ad30474103c9826147ab8c7fe1f0751a (diff)
downloadleetcode-19c811f19b9732c8166e632535d1262093ae5006.tar.gz
leetcode-19c811f19b9732c8166e632535d1262093ae5006.zip
932. beautiful array
Diffstat (limited to 'beautiful_array.c')
-rw-r--r--beautiful_array.c64
1 files changed, 64 insertions, 0 deletions
diff --git a/beautiful_array.c b/beautiful_array.c
new file mode 100644
index 0000000..d384066
--- /dev/null
+++ b/beautiful_array.c
@@ -0,0 +1,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);
+}