Resonant Carrier Frequency Queue - Google Online Assessment 16 Aug 2026

Problem Preview

"The signal engineers at Meridian Relay Station line up incoming station broadcasts in the order they arrive, feeding them one at a time into a **listening window** that can only hold a fixed number of the most recent broadcasts before the oldest one is dropped from the front. Every broadcast carries an integer frequency, and the station's master dial is tuned to a fixed **carrier value** that never changes during the process. A broadcast is considered **usable** by the relay only when its frequency is **coprime with the carrier value** — i.e., the frequency and carrier value have no common factor other than `1`. Anything that is not coprime is treated as interference and ignored for that window, even though it still occupies a slot and eventually gets pushed out like every other broadcast. Among the usable broadcasts currently present in the window, the engineers care about one particular number attached to each frequency: **how many integers from `1` up to that frequency are themselves coprime with it**. This value is the **Euler Totient Function**: `φ(x) = count of integers i (1 ≤ i ≤ x) such that gcd(i, x) = 1` Each time the window becomes full, the engineers record the **largest such value** among the currently usable broadcasts. If none of the broadcasts in the window is usable, nothing is recorded. After every broadcast has passed through and the window has slid all the way to the end of the queue, the relay reports the **sum of all values recorded along the way**. You are given a sequence of incoming frequencies, the window size, and the carrier value. Determine the final total reported by the relay. ### Function Description Implement the function: `sumMaxCoprimeTotient` ### Parameters * `n` — the number of incoming broadcasts/frequencies. * `k` — the fixed size of the listening window. * `carrier` — the fixed carrier value used to determine whether a frequency is usable. * `frequencies[]` — an array containing the incoming frequencies in their arrival order. ### Requirements * Frequencies must be processed in their original order. * The window always contains at most `k` most recent frequencies. * When a new frequency enters a full window, the oldest frequency is removed. * A frequency is usable only if: `gcd(frequency, carrier) == 1` * For every usable frequency `x`, calculate `φ(x)`. * Whenever the window is full, take the maximum `φ(x)` among all usable frequencies currently in the window. * If no frequency in the window is usable, record `0`/nothing for that window. * Return the sum of all recorded maximum values. ### Example Concept For a frequency `x`: ```text φ(x) = number of integers from 1 to x that are coprime with x ``` For example: ```text x = 10 Numbers coprime with 10: 1, 3, 7, 9 Therefore: φ(10) = 4 ``` If the current window contains several usable frequencies, compute their totient values and take the **maximum**. The answer is the sum of these maximum values over all full sliding-window positions."