Gray Code — LeetCode 89 Python Solution
- Problem
- #89
- Pattern
- Backtracking
- Reading time
- 2 min
- Source
- leetcode.com
The problem
An n-bit gray code sequence is a sequence of 2n integers where: Every integer is in the inclusive range [0, 2n - 1], The first integer is 0, An integer appears no more than once in the sequence, The binary representation of every pair of adjacent integers differs by exactly one bit, and The binary representation of the first and last integers differs by exactly one bit. Given an integer n, return any valid n-bit gray code sequence.
Example
- Input
- n = 2
- Output
- [0,1,3,2]
- Explanation
- The binary representation of [0,1,3,2] is [00,01,11,10].
Python solution
class Solution:
def grayCode(self, n: int) -> List[int]:
return [i ^ (i >> 1) for i in range(1 << n)]Complexity
| Measure | Complexity |
|---|---|
| Time | O(2^n), where n is the integer given in the problem |
| Space | O(1) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 89. Gray Code is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 89. Gray Code?
- LeetCode 89. Gray Code is rated Medium on LeetCode.
- What is the time complexity of LeetCode 89. Gray Code?
- The Python solution on this page runs in O(2^n), where n is the integer given in the problem.
- What is the space complexity of LeetCode 89. Gray Code?
- The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 89. Gray Code cover?
- LeetCode 89. Gray Code is tagged Bit Manipulation, Math and Backtracking on LeetCode.