786. Gray Code — i-th Element Using Recursion

MediumRecursionRecursion

The n-bit Gray code sequence is a list of 2^n integers where each consecutive pair differs by exactly one bit, starting from 0. The standard reflected Gray code gives the i-th element (0-indexed) as i XOR (i >> 1). Given integers n (the bit width) and i (the 0-based index, 0 <= i < 2^n), return the i-th element of the n-bit Gray code sequence. You may compute this recursively using the reflected construction: for the first half, the n-bit Gray code is the (n-1)-bit code; for the second half, it is the (n-1)-bit code in reverse with the MSB set.

Input: Two integers n and i separated by a comma.

Output: Return an integer — the i-th Gray code element.

Examples

Example 1
Input: 2, 0
Output: 0
Explanation: 2-bit Gray code is [0,1,3,2]; index 0 is 0.
Example 2
Input: 2, 2
Output: 3
Explanation: Index 2 is 3 (binary 11).
Example 3
Input: 3, 5
Output: 7
Explanation: 3-bit Gray code: [0,1,3,2,6,7,5,4]; index 5 is 7.

Constraints

Asked by

AmazonMicrosoftGoogleAdobeFlipkart
Solve this problem in the editor →