aboutsummaryrefslogtreecommitdiff
path: root/grey_code.c
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-05 00:19:20 -0700
committerJack Sangdahl <[email protected]>2025-03-05 00:19:20 -0700
commit63f2810c6d4c7081be8ac26b6a70f9323b4ddcd1 (patch)
tree1254b8d7f77656497abb73ef401c46a425a93cce /grey_code.c
parent744f3716db1a2504b730a3f412be1b0516f61450 (diff)
downloadleetcode-63f2810c6d4c7081be8ac26b6a70f9323b4ddcd1.tar.gz
leetcode-63f2810c6d4c7081be8ac26b6a70f9323b4ddcd1.zip
89. count gray code
Diffstat (limited to 'grey_code.c')
-rw-r--r--grey_code.c37
1 files changed, 37 insertions, 0 deletions
diff --git a/grey_code.c b/grey_code.c
new file mode 100644
index 0000000..1b2cd00
--- /dev/null
+++ b/grey_code.c
@@ -0,0 +1,37 @@
+// 89. Gray Code
+#include "leetcode.h"
+
+/*
+ * an n-bit gray code sequence is a sequence of '2^n' integers where every
+ * integer is in the inclusive range '[0, 2^n - 1]', the first integer is 0, an
+ * integer appears no more than once in the sequence, the binary representation
+ * of every pair of adjacent integers differs by exactly one bit and the binary
+ * representation of the first and last integers differs by exactly one bit.
+ * given an integer 'n', return any valid n-bit gray code sequence
+ */
+
+int convert(int n) { return n ^ (n >> 1); }
+
+int *grayCode(int n, int *returnSize) {
+ int base = 1;
+ for (int i = 0; i < n; i++)
+ base *= 2;
+ *returnSize = base;
+ int *ans = (int *)calloc(base, sizeof(int));
+ for (int i = 0; i < base; i++)
+ ans[i] = convert(i);
+ return ans;
+}
+
+int main() {
+ int rs1, *gc1 = grayCode(2, &rs1);
+ int rs2, *gc2 = grayCode(1, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d", gc1[i]); // expect: 0 1 3 2
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d", gc2[i]); // expect: 0 1
+ printf("\n");
+ free(gc1);
+ free(gc2);
+}