Implement Kac ring with O(1) color and kstep

Q: Implement Kac ring with O(1) color and kstep

This question evaluates understanding of algorithmic state representation, modular arithmetic, and efficient update/query design by requiring a Kac ring implementation that supports constant-time k-step advancement and O(1) aggregate color reporting.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are implementing a Kac ring dynamical system.

Model

There are N positions arranged in a circle, indexed clockwise: 0, 1, ..., N-1 .
Each position holds exactly one ball, whose color is either white or black .
A subset of positions is marked .
Initially ( time t = 0 ), all balls are white .

One time step

At each step:

Every ball moves one position clockwise : a ball at position i moves to position (i + 1) mod N .
If a ball leaves a marked position (i.e., it was at a marked index before moving), it flips color (white ↔ black) as it moves.

Task

Implement a class/data structure with the following interface:

Initialization

KacRing(N, marked)

N : number of positions.
marked : a sorted list of distinct marked indices 0 <= y1 < ... < ym < N .

Methods

step()
- Advances the system by exactly 1 time step.
kstep(k)
- Advances the system by k time steps.
- Must run in O(1) time per call (i.e., it must not loop for k steps).
color()
- Returns the value:

$\frac{W - B}{N}$

 where `W` is the current number of white balls and `B` is the current number of black balls.

Must run in O(1) time.

Notes / Constraints

Assume 1 <= N .
0 <= len(marked) <= N .
k can be very large (e.g., up to 10^18 ), so kstep cannot simulate step-by-step.
You do not need to expose individual ball colors; only the required methods above.