Count White Balls After K Steps

Q: Count White Balls After K Steps

This question evaluates understanding of modular arithmetic, parity tracking, periodic behavior on circular data structures, and the design of efficient preprocessing for repeated queries.

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 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.

Count White Balls After K Steps

Quick Overview

Comments (0)