From 63f2810c6d4c7081be8ac26b6a70f9323b4ddcd1 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Wed, 5 Mar 2025 00:19:20 -0700 Subject: 89. count gray code --- grey_code.c | 37 +++++++++++++++++++++++++++++++++++++ 1 file changed, 37 insertions(+) create mode 100644 grey_code.c (limited to 'grey_code.c') 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); +} -- cgit v1.2.3