A locksmith is certifying a vault with n independent tumblers, each either engaged (1) or disengaged (0). A combination is therefore an integer between 0 and 2^n - 1, read as the tumblers' states in binary (for n = 3, combination 5 means the tumblers read 101). The vault's stepper motor has a defect: in a single step it can only toggle exactly one tumbler, moving the vault from its current combination to a new combination that differs from it in exactly one bit.
During certification the locksmith must drive the vault starting from a given combination start, pass through every one of the 2^n possible combinations exactly once, and then perform one final single-tumbler-flip step that returns the vault to start, closing the loop. Output any sequence of combinations that satisfies this: it must begin with start, list all 2^n combinations exactly once, and every consecutive pair in the sequence (including the pair formed by the last and the first, wrapping around) must differ in exactly one bit.
A single line with two space-separated integers n and start.
Print the 2^n combinations of the cycle on one line, space-separated, starting with start.
1 <= n <= 100 <= start < 2^nExample 1
Input
2 0
Expected
0 1 3 2
Explanation
n=2 gives 4 combinations. Starting at 0 (00): 0(00) -> 1(01) flips bit 0; 1(01) -> 3(11) flips bit 1; 3(11) -> 2(10) flips bit 0; and closing the loop, 2(10) -> 0(00) flips bit 1. Every step and the wraparound flip exactly one tumbler, so "0 1 3 2" is valid.
Example 2
Input
3 5
Expected
5 4 6 7 3 2 0 1
Explanation
n=3 gives 8 combinations, starting at 5 (101). One valid cycle is "5 4 6 7 3 2 0 1": in binary 101,100,110,111,011,010,000,001, where each adjacent pair (and the wraparound pair 001->101) differs in exactly one bit.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →