Overflow in intermediate arithmetic
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Move from brute-force thinking to an efficient approach using math strategy.
An n-bit gray code sequence is a sequence of 2n integers where:
[0, 2n - 1],0,Given an integer n, return any valid n-bit gray code sequence.
Example 1:
Input: n = 2 Output: [0,1,3,2] Explanation: The binary representation of [0,1,3,2] is [00,01,11,10]. - 00 and 01 differ by one bit - 01 and 11 differ by one bit - 11 and 10 differ by one bit - 10 and 00 differ by one bit [0,2,3,1] is also a valid gray code sequence, whose binary representation is [00,10,11,01]. - 00 and 10 differ by one bit - 10 and 11 differ by one bit - 11 and 01 differ by one bit - 01 and 00 differ by one bit
Example 2:
Input: n = 1 Output: [0,1]
Constraints:
1 <= n <= 16Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Math · Backtracking · Bit Manipulation
2
1
1-bit-and-2-bit-characters)import java.util.*;
class Solution {
public List<Integer> grayCode(int n) {
List<Integer> ans = new ArrayList<>();
ans.add(0);
for (int bit = 0; bit < n; bit++) {
int mask = 1 << bit;
for (int i = ans.size() - 1; i >= 0; i--) {
ans.add(ans.get(i) | mask);
}
}
return ans;
}
}
func grayCode(n int) []int {
ans := []int{0}
for bit := 0; bit < n; bit++ {
mask := 1 << bit
for i := len(ans) - 1; i >= 0; i-- {
ans = append(ans, ans[i]|mask)
}
}
return ans
}
class Solution:
def grayCode(self, n: int) -> List[int]:
ans = [0]
for bit in range(n):
mask = 1 << bit
for x in reversed(ans):
ans.append(x | mask)
return ans
impl Solution {
pub fn gray_code(n: i32) -> Vec<i32> {
let mut ans = vec![0];
for bit in 0..n {
let mask = 1 << bit;
for i in (0..ans.len()).rev() {
ans.push(ans[i] | mask);
}
}
ans
}
}
function grayCode(n: number): number[] {
const ans: number[] = [0];
for (let bit = 0; bit < n; bit++) {
const mask = 1 << bit;
for (let i = ans.length - 1; i >= 0; i--) {
ans.push(ans[i] | mask);
}
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Temporary multiplications exceed integer bounds.
Usually fails on: Large inputs wrap around unexpectedly.
Fix: Use wider types, modular arithmetic, or rearranged operations.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.