Count White Balls After K Steps
Company: Voleon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a ring of `N` positions indexed from `0` to `N-1`.
- At each position `i`, there is initially one ball whose color is either white or black.
- Each position may also contain a flip gate, represented by `gate[i]` where `1` means a gate is present and `0` means no gate.
- In one synchronous step, every ball moves one position clockwise.
- Whenever a ball crosses a position containing a flip gate, its color toggles.
For each query, you are given an integer `K` and must determine how many balls are white after exactly `K` steps.
Additional details:
- A ball starting at index `i` will be located at `(i + K) mod N` after `K` steps.
- Its final color depends only on whether it crosses an even or odd number of gates during those `K` moves.
- `K` may be much larger than `N`, so simulating step by step is too slow.
Design an algorithm that preprocesses the ring and answers each query efficiently, ideally in `O(1)` time per query after preprocessing.
Quick Answer: This question evaluates understanding of modular arithmetic, parity tracking, periodic behavior on circular data structures, and the design of efficient preprocessing for repeated queries.
You are given a ring of `N` positions indexed from `0` to `N-1`. Each position `i` starts with one ball whose color is white (`'W'`) or black (`'B'`), given by the string `colors`. Each position may contain a flip gate, given by the list `gates` where `gates[i] = 1` means a gate is present and `0` means no gate.
In one synchronous step, every ball moves one position clockwise (a ball at index `p` moves to `(p + 1) mod N`). Whenever a ball moves onto a position that contains a flip gate, its color toggles (white becomes black and vice versa).
You are also given a list `queries` of non-negative integers. For each value `K` in `queries`, determine how many balls are white after **exactly** `K` synchronous steps, starting fresh from the original configuration each time. Return a list of the answers, one per query, in order.
A ball starting at index `i` ends at `(i + K) mod N` and crosses the positions `i+1, i+2, ..., i+K` (mod N) along the way; its final color depends only on the parity of how many of those crossings land on a gate. `K` may be far larger than `N`, so per-step simulation is too slow — preprocess the ring so each query is answered in `O(1)` time.
Constraints
- 0 <= N (ring size = len(colors) = len(gates))
- colors[i] is 'W' or 'B'
- gates[i] is 0 or 1
- 0 <= K, and K may be much larger than N
- 0 <= number of queries
Examples
Input: ("WBWB", [0, 1, 0, 0], [0, 1, 4])
Expected Output: [2, 1, 2]
Explanation: K=0: original WBWB has 2 whites. K=1: each ball steps once; gate sits at index 1 so only the ball that lands there toggles -> 1 white. K=4 is exactly one full lap (N=4): every ball crosses the single gate once and toggles, WBWB -> BWBW, still 2 whites.
Input: ("W", [1], [0, 1, 2, 3])
Expected Output: [1, 0, 1, 0]
Explanation: Single white ball on a 1-position ring whose only cell has a gate. Each step the ball re-enters the gated cell and toggles, so the white count alternates 1,0,1,0 with the parity of K.
Hints
- A ball at index i ends at (i + K) mod N, but its final color depends only on the PARITY of how many gates it crosses, not on where it lands.
- Split K into full laps and a remainder: K = full*N + rem. Every full lap crosses every gate exactly once, contributing full * (total gates) crossings to every ball.
- For the remaining 'rem' steps a ball from index i crosses gates at positions i+1 .. i+rem. Use a prefix-sum array over the gates duplicated once to evaluate this wrap-around window in O(1).
- Final color is white XOR (total crossings is odd). Sum that over all i to get the white count for each query.