Loading...
Loading...
Loading...
Pooja is designing a dial for a college robot. Each position of the dial shows an n-bit code, and two neighbouring positions must differ in exactly one bit, so a sensor never misreads a turn.
She builds the list of codes with this rule. For n = 1 the list is 0, 1. For a larger n, take the list for n - 1 and put 0 in front of every code. Then take the same list in reverse order and put 1 in front of every code. Join the two parts.
For n = 2 this gives 00, 01, 11, 10. Positions are numbered from 0. Print the codes at positions a to b.
Example 1
Input
2 0 3
Output
00 01 11 10
The whole list for n = 2: 00, 01, 11, 10.
Example 2
Input
3 2 5
Output
011 010 110 111
The list for n = 3 is 000, 001, 011, 010, 110, 111, 101, 100. Positions 2 to 5 are shown.
Try the problem first. Open one hint at a time.
You cannot build the list for n = 60: it has about 10^18 codes. Find each position on its own.
The first half of the list (positions below 2^(n-1)) is the list for n - 1 with a 0 in front, in the same order.
In the second half, position k shows 1 followed by the code at position 2^n - 1 - k of the list for n - 1, because that half is reversed.
Write a method code(n, k) that calls itself with n - 1. Use long and 1L << n for the positions.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor