Gray Code at an Index
Medium About 15 min Free, no account needed
The n-th Gray code without generating the first n-1.
The brief
The Gray code sequence lists all binary numbers so that consecutive values
differ in exactly one bit: 0, 1, 3, 2, 6, 7, 5, 4, ... (the reflected code).
Given an index i (up to 10^12), return the i-th Gray code.
The obvious approach generates the sequence by reflection until it reaches index i,
fine for small indexes, far too slow (in time and memory) at the hidden
10^12. You will need to compute the i-th value directly, without building
the sequence.
Starter code
using System;
public class Solution
{
// TODO: return the i-th value of the reflected Gray code sequence.
public long GrayCode(long i)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
What it practices
- Bit manipulation
- Use masks, shifts and XOR on the binary representation directly.
Related katas
- Modular Exponentiation Medium Free Raise to a power of 10^18 - one squaring at a time.
- Counting Bits Easy Free Popcounts for 0..n - reuse the table you are already building.
- Power of Two Easy Free One bit trick, two edge cases waiting to bite.
- Reverse Bits Easy Free Reverse a 32-bit pattern - signed shifts will betray you.