aboutsummaryrefslogtreecommitdiff
path: root/pascals_triangle2.c
diff options
context:
space:
mode:
Diffstat (limited to 'pascals_triangle2.c')
-rw-r--r--pascals_triangle2.c46
1 files changed, 46 insertions, 0 deletions
diff --git a/pascals_triangle2.c b/pascals_triangle2.c
new file mode 100644
index 0000000..ef21edc
--- /dev/null
+++ b/pascals_triangle2.c
@@ -0,0 +1,46 @@
+// 119. Pascal's Triangle II
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/*
+ * given an integer 'row_index', return the 'row_index'th row of the pascals
+ * triangle. in pascals triangle, each number is the sum of the two numbers
+ * directly above it as shown.
+ */
+
+int *getRow(int row_index, int *return_size) {
+ uint val[34];
+ memset(val, 0, sizeof(val));
+ val[0] = 1;
+ *return_size = row_index + 1;
+ for (int i = 0; i < row_index; ++i) {
+ int prev = 1, j;
+ const int total = row_index + 1, half = total / 2;
+ for (j = 1; j < half; ++j) {
+ val[j] = prev + val[j];
+ prev = val[j] - prev;
+ val[total - j - 1] = val[j];
+ }
+ if (total & 1)
+ val[j] = prev + val[j];
+ val[total - 1] = 1;
+ }
+ return val;
+}
+
+int main() {
+ int rs1[] = {}, rs2[] = {}, rs3[] = {};
+ int *gr1 = getRow(3, rs1);
+ int *gr2 = getRow(0, rs2);
+ int *gr3 = getRow(1, rs3);
+ for (int i = 0; i < 4; i++)
+ printf("%d ", gr1[i]); // expect: 1 3 3 1
+ printf("\n");
+ for (int i = 0; i < 1; i++)
+ printf("%d ", gr2[i]); // expect: 1
+ printf("\n");
+ for (int i = 0; i < 2; i++)
+ printf("%d ", gr3[i]); // expect: 1 1
+ printf("\n");
+}