aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--grey_code.c37
-rw-r--r--grey_code.py28
2 files changed, 65 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);
+}
diff --git a/grey_code.py b/grey_code.py
new file mode 100644
index 0000000..3d9f565
--- /dev/null
+++ b/grey_code.py
@@ -0,0 +1,28 @@
+# 89. Gray Code
+
+"""
+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
+"""
+
+
+class Solution(object):
+ def grayCode(self, n):
+ """
+ :type n: int
+ :rtype: List[int]
+ """
+ ans = [0]
+ for i in range(n):
+ ans += [j + pow(2, i) for j in reversed(ans)]
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.grayCode(n=2))
+ print(obj.grayCode(n=1))