Interview Prepbit-manipulationmediumAmazonGoogleBloomberg

Gray Code

Choose your preparation mode4 modes available

Try It Solution Trace

📋

Problem

Imagine you need to design a sequence of binary codes for a rotary encoder where only one bit changes at a time to minimize errors during transitions.

Given a non-negative integer n representing the total number of bits in the code, generate a sequence of Gray codes. A Gray code sequence must begin with 0 and each successive number differs from the previous by exactly one bit. Return the sequence as a list of integers.

1 ≤ n ≤ 16

Edge cases: n = 0 → [0]n = 1 → [0, 1]n = 16 → large output but must be correct

</>

IDE

def grayCode(n: int) -> list:

def grayCode(n):
    # Write your solution here
    pass

class Solution {
    public List<Integer> grayCode(int n) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<int> grayCode(int n) {
    // Write your solution here
    return {};
}

function grayCode(n) {
    // Write your solution here
}

0/9

Common Bugs to Avoid

Wrong: [0,1,2,3]Generated binary counting sequence instead of Gray code; adjacent elements differ by multiple bits.✅ Use grayCode(i) = i ^ (i >> 1) instead of counting from 0 to 2^n-1 directly.

Wrong: [0]Incorrect handling of n>0 cases, returning only base case or empty sequence.✅ Ensure loop runs from 0 to 2^n - 1 and generates full sequence.

Wrong: Sequence with repeated elements or missing elementsBacktracking approach with incorrect pruning or state tracking.✅ Use direct formula or reflected code construction to avoid duplicates and missing values.

Wrong: Sequence length less than 2^nOff-by-one error in loop bounds or early termination.✅ Loop from 0 to 2^n - 1 inclusive to generate full sequence.

Wrong: Timeout or no output for large nUsing exponential backtracking or recursion for large n.✅ Implement O(2^n) bitwise formula generation to pass performance constraints.

✓

Test Cases

t1_01basic

Input{"n":2}

Expected[0,1,3,2]

The 2-bit Gray code sequence starts at 0 (00), then 1 (01), then 3 (11), then 2 (10). Each adjacent pair differs by one bit.

t1_02basic

Input{"n":3}

Expected[0,1,3,2,6,7,5,4]

3-bit Gray code sequence of length 8 where each adjacent pair differs by one bit.

Practice

(1/5)

1. You need to determine if a given positive integer can be expressed as 4 raised to some integer power (i.e., n = 4^k for k ≥ 0). Which approach guarantees an optimal O(1) time solution without loops or recursion?

easy

A. Use logarithms to check if log base 4 of the number is an integer.

B. Iteratively divide the number by 4 until it becomes 1 or a non-divisible remainder is found.

C. Check if the number is a power of two and then verify if the set bit is in an even position using bitmasking.

D. Use dynamic programming to build up powers of four and compare with the number.

2. Given the following code, what is the output of isPowerOfTwo(16) and isPowerOfTwo(218)?

def isPowerOfTwo(n: int) -> bool:
    if n <= 0:
        return False
    return bin(n).count('1') == 1

print(isPowerOfTwo(16))
print(isPowerOfTwo(218))

easy

A. True and False

B. False and True

C. True and True

D. False and False

4. Identify the bug in the following code that attempts to check if a number is a power of two:

def isPowerOfTwo(n: int) -> bool:
    while n % 2 == 0:
        n //= 2
    return n == 1

What is the issue?

medium

A. The return statement should check n == 0 instead of n == 1

B. The loop condition should be n > 1 instead of n % 2 == 0

C. Using integer division //= 2 causes infinite loops for odd numbers

D. The code does not handle zero or negative inputs, leading to incorrect results

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Gray Code

Practice

Solution

Step 1: Understand the problem requirement

Step 2: Evaluate approaches for O(1) time

Final Answer:

Quick Check:

Solution

Step 1: Trace isPowerOfTwo(16)

Step 2: Trace isPowerOfTwo(218)

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that efficiently tracks continuation bytes

Final Answer:

Quick Check:

Solution

Step 1: Analyze input handling

Step 2: Consequence of missing check

Final Answer:

Quick Check:

Solution

Step 1: Identify how subsets are added to results

Step 2: Fix by appending a copy of `path`

Final Answer:

Quick Check:

Ready to prove it?

Practice

Solution

Step 1: Understand the problem requirement

Step 2: Evaluate approaches for O(1) time

Final Answer:

Quick Check:

Solution

Step 1: Trace isPowerOfTwo(16)

Step 2: Trace isPowerOfTwo(218)

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Identify the approach that efficiently tracks continuation bytes

Final Answer:

Quick Check:

Solution

Step 1: Analyze input handling

Step 2: Consequence of missing check

Final Answer:

Quick Check:

Solution

Step 1: Identify how subsets are added to results

Step 2: Fix by appending a copy of path

Final Answer:

Quick Check:

Ready to prove it?

Step 2: Fix by appending a copy of `path`