Reflected Binary Code

Given an integer n, return the nth (0-indexed) gray code number. Gray code is a way of ordering binary numbers such that each consecutive number’s values differ by exactly one bit.

The first few gray codes are: [0, 1, 11, 10, 110, 111, ...]

Constraints

• 0 ≤ n ≤ 1,000,000

https://binarysearch.com/problems/Reflected-Binary-Code

Examples

Example 1

Input

• n = 3

Output

• answer = 2

Solution