diff options
author | Jack Sangdahl <[email protected]> | 2025-03-05 00:19:20 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-05 00:19:20 -0700 |
commit | 63f2810c6d4c7081be8ac26b6a70f9323b4ddcd1 (patch) | |
tree | 1254b8d7f77656497abb73ef401c46a425a93cce /grey_code.c | |
parent | 744f3716db1a2504b730a3f412be1b0516f61450 (diff) | |
download | leetcode-63f2810c6d4c7081be8ac26b6a70f9323b4ddcd1.tar.gz leetcode-63f2810c6d4c7081be8ac26b6a70f9323b4ddcd1.zip |
89. count gray code
Diffstat (limited to 'grey_code.c')
-rw-r--r-- | grey_code.c | 37 |
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); +} |