Gray Code
Print all n-bit Gray codes so that consecutive strings differ in exactly one bit.
Problem Summary
Original task summary for this archive page. The official CSES statement is linked in the header instead of being mirrored here.
Generate all binary strings of length \(n\) in an order where every consecutive pair differs in exactly one bit.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
A standard closed-form construction exists for Gray code: \[ g(i) = i \oplus (i \gg 1), \] where \(i\) runs from \(0\) to \(2^n - 1\).
Why does this help? Consecutive integers differ at one lowest changed bit plus a block of lower bits, and the xor-with-shift transformation folds that pattern into a representation where only one output bit changes between neighbors.
So we can:
iterate \(i\) from \(0\) to \(2^n - 1\)
compute \(g(i)\)
print \(g(i)\) as a binary string of exactly \(n\) bits
This is much simpler than building the list recursively, although the recursive reflection construction would also be valid.
Pseudocode
Natural algorithm flow before dropping to the concrete C++ implementation.
Set the limit to \(2^n\).
For each integer \(i\) from \(0\) to \(\text{limit} - 1\):
compute \(g = i \oplus (i \gg 1)\)
print the \(n\)-bit binary representation of \(g\)
Complexity Analysis
Time and memory costs for the approach used in the implementation below.
Time: \(O(n \cdot 2^n)\), dominated by printing \(2^n\) strings of length \(n\)
Memory: \(O(1)\) besides the output itself
C++ Solution
The exact repository source used for this solution page.
#include <iostream>
int main() {
int n;
std::cin >> n;
const int limit = 1 << n;
for (int i = 0; i < limit; ++i) {
const int gray = i ^ (i >> 1);
for (int bit = n - 1; bit >= 0; --bit) {
std::cout << ((gray >> bit) & 1);
}
std::cout << '\n';
}
return 0;
}
Notes / Pitfalls
Short reminders about edge cases, construction details, or common mistakes.
Make sure to print leading zeroes so every line has exactly \(n\) characters.
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.