Bird
Raised Fist0
Interview Prepbit-manipulationmediumAmazonGoogleBloomberg

Gray Code

Choose your preparation mode4 modes available
Try ItSolutionTrace
▶
Steps
setup

Initialize variables and start loop

We start with n=2, meaning we will generate Gray codes for numbers 0 through 3. The list to hold Gray codes is empty initially.

💡 Setting up the range and empty list prepares us to compute Gray codes for all numbers in the sequence.
Line:return [i ^ (i >> 1) for i in range(1 << n)]
💡 The range 0 to 3 covers all 2-bit numbers, ensuring a complete Gray code sequence.
📊
Gray Code - Watch the Algorithm Execute, Step by Step
Watching this step-by-step bitwise operation reveals how Gray codes ensure only one bit changes between consecutive numbers, a key property that is not obvious from the formula alone.
Step 1/14
·Active fill★Answer cell
Initialize
A
0
0
0
0
0
0
0
0
=0
B
Shift Right i by 1
A
0
0
0
0
0
0
0
0
=0
B
0
0
0
0
0
0
0
0
=0
💡 Right shift prepares second operand for XOR
XOR i and i>>1
A
0
0
0
0
0
0
0
0
=0
B
0
0
0
0
0
0
0
0
=0
────────────────
=
0
0
0
0
0
0
0
0
=0
💡 XOR of identical bits yields 0
Append Gray code
A
0
0
0
0
0
0
0
0
=0
B
0
0
0
0
0
0
0
0
=0
────────────────
=
0
0
0
0
0
0
0
0
=0
💡 First Gray code appended
Shift Right i by 1
A
0
1
=1
B
0
0
0
0
0
0
0
0
=0
💡 Right shift prepares second operand for XOR
XOR i and i>>1
A
0
1
=1
B
0
0
0
0
0
0
0
0
=0
────
=
0
1
=1
💡 XOR of differing bits yields 1
Append Gray code
A
0
1
=1
B
0
0
0
0
0
0
0
0
=0
────
=
0
1
=1
💡 Second Gray code appended
Shift Right i by 1
A
0
1
0
=2
B
0
1
=1
💡 Right shift prepares second operand for XOR
XOR i and i>>1
A
0
1
0
=2
B
0
1
=1
──────
=
0
1
1
=3
💡 XOR flips bits where operands differ
Append Gray code
A
0
1
0
=2
B
0
1
=1
──────
=
0
1
1
=3
💡 Third Gray code appended
Shift Right i by 1
A
0
1
1
=3
B
0
1
=1
💡 Right shift prepares second operand for XOR
XOR i and i>>1
A
0
1
1
=3
B
0
1
=1
──────
=
0
1
0
=2
💡 XOR flips bits where operands differ
Append Gray code
A
0
1
1
=3
B
0
1
=1
──────
=
0
1
0
=2
💡 Fourth Gray code appended
Return Gray code list
A
0
1
1
=3
B
0
1
=1
──────
=
0
1
0
💡 Final Gray code sequence returned

Key Takeaways

✓ Gray code for any number i can be computed directly using the formula i ^ (i >> 1).

This insight is hard to see from code alone because the XOR and shift operations are bitwise and non-intuitive without visualization.

✓ Each Gray code differs from the previous by exactly one bit, visible by comparing consecutive result_bits.

Seeing the bits change one at a time clarifies the Gray code property that is not obvious from the numeric output.

✓ Right-shifting i by one bit aligns bits for XOR to produce the Gray code, showing the role of bit manipulation in the formula.

Understanding why the shift is needed is easier when watching the bits side-by-side rather than reading the formula.

Practice

(1/5)
1. Given the following code, what is the value of ones after processing the input [2, 2, 3, 2]?
easy
A. 3
B. 0
C. 2
D. 1

Solution

  1. Step 1: Trace variable updates for each num

    After processing 2,2,3,2, the variable 'ones' ends up holding the unique number 3.

  2. Step 2: Confirm final return value

    The function returns 'ones' which is 3, the single number appearing once.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Output matches expected unique element 3 [OK]
Hint: Final 'ones' holds the unique element after all iterations [OK]
Common Mistakes:
  • Confusing 'ones' and 'twos' variables
  • Off-by-one iteration errors
2. You are given an array where every element appears exactly twice except for one element that appears only once. Which approach guarantees finding the unique element in linear time and constant space?
easy
A. Using a dynamic programming approach to track element counts
B. Sorting the array and then scanning to find the unique element
C. Using a brute force nested loop to count occurrences of each element
D. Using XOR operation to cancel out duplicates and find the single element

Solution

  1. Step 1: Understand problem constraints

    Every element except one appears twice, so duplicates cancel out under XOR.

  2. Step 2: Identify approach that leverages XOR properties

    XOR of a number with itself is zero, and XOR with zero is the number itself, so XORing all elements leaves the unique one.

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    XOR approach runs in O(n) time and O(1) space [OK]
Hint: XOR cancels duplicates perfectly [OK]
Common Mistakes:
  • Sorting is O(n log n), not optimal
  • Brute force is O(n²), inefficient
  • DP is unrelated to this problem
3. What is the time complexity of the brute force iterative division approach to check if a number n is a power of four?
medium
A. O(1) because division is constant time
B. O(n) because it checks every number up to n
C. O(log log n) because division by 4 reduces n faster than by 2
D. O(log n) because the number is divided by 4 each iteration

Solution

  1. Step 1: Analyze the loop iterations

    Each iteration divides n by 4, so the number of iterations is proportional to log base 4 of n.

  2. Step 2: Express complexity in Big-O notation

    Since log base 4 of n is O(log n), the time complexity is O(log n).

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Loop runs ~log4(n) times, which is O(log n) [OK]
Hint: Dividing by 4 reduces n logarithmically -> O(log n)
Common Mistakes:
  • Confusing division steps as O(1)
  • Mistaking log log n complexity
4. Consider this buggy code snippet for finding two unique numbers. Which line contains the subtle bug?
medium
A. Line 8: set_bit calculation
B. Line 6: xor calculation loop
C. Line 3: xor initialization
D. Line 12: partitioning condition

Solution

  1. Step 1: Identify how set_bit is computed

    Correct approach uses set_bit = xor & (-xor) to isolate rightmost set bit. Here, set_bit = xor misses this step.

  2. Step 2: Understand impact of bug

    Without isolating rightmost set bit, partitioning fails, XOR groups won't separate unique numbers correctly.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Bug in set_bit calculation breaks partitioning [OK]
Hint: Isolate rightmost set bit with xor & (-xor) [OK]
Common Mistakes:
  • Using xor directly as set_bit
  • Breaking early before full XOR
  • Misusing partition condition
5. Suppose you want to count the number of set bits for all integers from 0 to n, but now n can be negative as well (e.g., from -n to n). Which modification to the Brian Kernighan's bit counting approach correctly handles this scenario?
hard
A. Apply the same algorithm directly to negative numbers since bitwise operations work the same.
B. Skip negative numbers because bit counting is undefined for them.
C. Convert negative numbers to their two's complement 32-bit unsigned representation before counting bits.
D. Use string conversion of the absolute value of negative numbers and count '1's.

Solution

  1. Step 1: Understand bit representation of negatives

    Negative integers are represented in two's complement form, so counting bits requires interpreting them as unsigned 32-bit integers.

  2. Step 2: Modify algorithm accordingly

    Convert negative numbers to their 32-bit unsigned equivalent before applying Kernighan's trick to count set bits correctly.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Two's complement conversion ensures correct bit counting for negatives [OK]
Hint: Negative bits require two's complement conversion [OK]
Common Mistakes:
  • Applying algorithm directly to negatives
  • Ignoring negatives
  • Using absolute value without conversion
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