Code (Gray Codes)

Problem Statement Generate a Gray code of N bits: a cyclic sequence of all 2^N binary strings of length N such that consecutive strings (including the last and first) differ in exactly one bit. Solution Approach Refle...

Updated May 21, 2026

Track IOI

Year 1999

Statement Rendered from TeX

TeXC++Rendered statement

Problem statement

Problem Statement

Rendered from the "Problem Statement" section in the LaTeX write-up.

Open TeX section

Generate a Gray code of $N$ bits: a cyclic sequence of all $2^N$ binary strings of length $N$ such that consecutive strings (including the last and first) differ in exactly one bit.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Solution Approach

Reflected Gray Code

The reflected Gray code is constructed recursively:

Base: For $N = 1$, the code is $(0, 1)$.
Step: Given the $(N{-}1)$-bit Gray code $G_{N-1} = (g_0, g_1, \ldots, g_{2^{N-1}-1})$, the $N$-bit code is: \[ (0g_0,\; 0g_1,\; \ldots,\; 0g_{2^{N-1}-1},\; 1g_{2^{N-1}-1},\; \ldots,\; 1g_1,\; 1g_0). \]

Direct Formula

The $i$-th Gray code word (0-indexed) is: \[ g(i) = i \oplus \lfloor i/2 \rfloor, \] where $\oplus$ is bitwise XOR. This yields an $O(1)$-per-word method.

Proof (Proof that consecutive words differ in exactly one bit).

Consider $g(i) = i \oplus (i \gg 1)$ and $g(i{+}1) = (i{+}1) \oplus ((i{+}1) \gg 1)$. Let $i$ have trailing bits $0\underbrace{1\cdots1}_k$. Then $i+1$ flips these $k{+}1$ bits. We have $i \oplus (i{+}1) = 2^{k+1} - 1$ (a mask of $k{+}1$ ones) and $(i \gg 1) \oplus ((i{+}1) \gg 1) = 2^k - 1$ (a mask of $k$ ones). Their XOR is $g(i) \oplus g(i{+}1) = 2^k$, which has exactly one bit set.

C++ Solution

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);

    long long total = 1LL << N;

    for (long long i = 0; i < total; i++) {
        long long gray = i ^ (i >> 1);
        for (int bit = N - 1; bit >= 0; bit--)
            putchar('0' + ((gray >> bit) & 1));
        putchar('\n');
    }

    return 0;
}

Complexity Analysis

Time complexity: $O(2^N \cdot N)$. Each of the $2^N$ code words requires $O(N)$ time to print.
Space complexity: $O(1)$ beyond the output (each word is computed and printed on the fly).

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 1999 - Code (Gray Codes)
// Generate an N-bit reflected Gray code: all 2^N binary strings such that
// consecutive strings differ in exactly one bit (cyclic).
// Approach: g(i) = i XOR (i >> 1) gives the i-th Gray code word in O(1).
// Complexity: O(2^N * N) time, O(N) space.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    // Edge case: N = 0 means just one empty string
    if (N == 0) {
        cout << "\n";
        return 0;
    }

    long long total = 1LL << N;

    for (long long i = 0; i < total; i++) {
        long long gray = i ^ (i >> 1);
        // Print N-bit binary representation, MSB first
        for (int bit = N - 1; bit >= 0; bit--) {
            cout << ((gray >> bit) & 1);
        }
        cout << "\n";
    }

    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/1999/code/solution.texC++ implementationcompetitive_programming/ioi/1999/code/solution.cpp