What is the time and space complexity of Gray Code?

Time complexity: O(2^n). Space complexity: O(2^n).

Gray Code

Med

Code

Loading editor...

Tap Analyze to see visualization

Click Analyze to visualize

See step-by-step execution, variables, and output

Variables

Run code to see variables

Output

Console output will appear here

Press Space to start•← → to step•? all shortcuts

Solution Guide: Gray Code

Approach

Generate 2^n Gray codes using the formula gray(i) = i ^ (i >> 1). Iterate from 0 to 2^n - 1 and apply the formula to each index. Adjacent values in the sequence differ by exactly one bit.

Complexity Analysis

Time: O(2^n)
Space: O(2^n)

Pattern

Bit Shifting

Why It Works

XOR-ing a number with its right-shifted self flips at most one bit between consecutive integers, which is exactly the Gray code property.

Updated Mar 2026