Lantern Ring Relay
HardOnline Assessment
Find which lanterns of a ring are lit after a very long time, when each one copies a simple rule about its neighbours.
A festival hangs n lanterns in a ring, numbered 0 to n - 1; lantern n - 1 is next to lantern 0. lanterns is a string of n characters, 1 for lit and 0 for dark. Every minute all lanterns change at the same moment: a lantern is lit in the next minute exactly when exactly one of its two neighbours is lit now. Its own state does not matter.
For example, in a ring of 5 lanterns, 00100 becomes 01010 after one minute and 10001 after two.
Input: lanterns, a string of 0 and 1 with 3 <= n; minutes, how many minutes pass.
Output: the string of n characters describing the ring after minutes minutes. With minutes = 0 that is the original string.
Example 1
- Input:
- ["00100",2]
- Output:
- "10001"
- Explanation
- Only lantern 2 is lit. Lanterns 1 and 3 each have exactly one lit neighbour, so after one minute the ring is 01010. In the next minute lantern 0 has neighbours 4 (dark) and 1 (lit), so it lights; lantern 4 likewise sees only lantern 3 lit; lantern 1 sees lanterns 0 and 2, both dark; lantern 2 sees lanterns 1 and 3, both lit, so it goes dark; lantern 3 sees only dark neighbours. The result is 10001.
Example 2
- Input:
- ["1000000",1000000000000000]
- Output:
- "0110011"
- Explanation
- A single lit lantern in a ring of 7 produces 0100001, 0010010, 0101101, 0001100, 0011110, 0110011 and 0111111 in the next seven minutes, and the eighth minute gives 0100001 again. So from minute 1 on the ring repeats every 7 minutes. Since (1015 - 1) mod 7 = 5, minute 1015 shows the same ring as minute 6: 0110011. Simulating every minute is hopeless; skip whole periods or jump several minutes at once.
Example 3
- Input:
- ["10110100",1000000000000000]
- Output:
- "00000000"
- Explanation
- With 8 lanterns the ring 10110100 becomes 00110011, then 11111111 (each lantern has exactly one lit neighbour), and then 00000000 because every lantern sees two lit neighbours. A fully dark ring stays dark, so after any number of minutes from 3 on the answer is 00000000.
Constraints
- 3 ≤ lanterns.length ≤ 200; every character is 0 or 1
- 0 ≤ minutes ≤ 1015