The problem
The Gray code of a whole number n is n ^ (n >> 1) (lesson 2). Given a Gray code g, return the n it came from. There is always exactly one.
from_gray(6) # 4, because 4 ^ 2 == 6
from_gray(0) # 0
from_gray(7) # 5: 101 ^ 010 == 111
Limits
gis 0 or more, with up to 1,000,000 bits. The two biggest tests have 2 seconds each.- A loop that shifts
gone place at a time is too slow for a million bits: each shift copies the whole number.
Builds on BITS-2 Bitwise operators.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
10 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | The example | Not run | |
| 2 | Zero | Not run | |
| 3 | One | Not run | |
| 4 | The 3-bit order | Not run | |
| 5 | All 4-bit codes | Not run | |
| 6 | A single 1 at the top | Not run | |
| 7 | Alternating bits | Not run | |
| 8 | Round trip up to 3,000 | Not run | |
| 9 | A million bits | Not run | |
| 10 | A million ones | Not run |