diff options
-rw-r--r-- | introductory_problems/gray_code.cpp | 23 | ||||
-rw-r--r-- | introductory_problems/readme.md | 7 |
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) |