Flipping Balls with Moving Marked Positions

Circular Light Flip Medium · Topics · Company Tags · Hints

Consider n lights placed around a circle, labeled 0 through n-1. Each light is either off (0) or on (1). Initially all lights are off.

Some positions are equipped with toggles. You are given the list initial of the starting indices of these toggles.

A single step consists of two actions performed in order:

1. Every toggle flips the light at its current index – off becomes on, on becomes off.
2. After flipping, every toggle advances clockwise to the next position: its new index becomes (current_index + 1) % n.

You must determine the state of every light after exactly k steps. Because k can be enormous, a simulation that runs step‑by‑step is too slow. Design an algorithm that returns the final array of states in O(n) time, independent of k.

---

Example 1:

Input:
4 1 3
0

Output:
1 1 1 0

Explanation:
Step 1: flip index 0 → [1,0,0,0], toggles move to [1].
Step 2: flip index 1 → [1,1,0,0], toggles move to [2].
Step 3: flip index 2 → [1,1,1,0], toggles move to [3]. Final state is 1 1 1 0.

---

Example 2:

Input:
3 2 2
0 1

Output:
1 0 1

---

Example 3:

Input:
1 1 5
0

Output:
1

---

Constraints:

• 1 ≤ n ≤ 100 000
• 0 ≤ m ≤ n
• 0 ≤ k ≤ 10¹⁵
• The initial m toggle positions are distinct integers between 0 and n-1.