summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--introductory_problems/gray_code.cpp23
-rw-r--r--introductory_problems/readme.md7
2 files changed, 30 insertions, 0 deletions
diff --git a/introductory_problems/gray_code.cpp b/introductory_problems/gray_code.cpp
new file mode 100644
index 0000000..9911cd4
--- /dev/null
+++ b/introductory_problems/gray_code.cpp
@@ -0,0 +1,23 @@
+// 2205. Gray Code
+#include <bits/stdc++.h>
+using namespace std;
+
+static int n;
+const int max_n = 16;
+static bool a[max_n + 1];
+
+void print(void) {
+ for (int i = n; i; i--)
+ printf("%d", a[i]);
+ printf("\n");
+}
+
+int main() {
+ scanf("%d", &n);
+ print();
+ for (int i = 1; i < 1 << n; i++) {
+ int lsb = __builtin_ffs(i);
+ a[lsb] ^= 1;
+ print();
+ }
+}
diff --git a/introductory_problems/readme.md b/introductory_problems/readme.md
index 4fee2d6..3adac29 100644
--- a/introductory_problems/readme.md
+++ b/introductory_problems/readme.md
@@ -83,3 +83,10 @@ Given a string, your task is to reorder its letters in such a way that it become
**Input**: The only input line has a string of length `n` consisting of characters A-Z. (Example: AAAACACBA)
**Output**: Print a palindrome consisting of the characters of the original string. You may print any valid solution. If there are no solutions, print "NO SOLUTIONS". (Example: AACABACAA)
+
+### Gray Code
+A gray code is a list of `2^n` bit strings of length `n`, where any two successive strings differ in exactly one bit (ie. their hamming distance is one). Your task is to create a gray code for a given length `n`.
+
+**Input**: The only input line has an integer `n`. (Example: 2)
+
+**Output**: Print `2^n` lines that describes the gray code. You can print any valid solution. (Example: 00 01 11 10)