Signal Pings
Learn this problem
VisaNEW GRADOAProblem statement
You have an array of n binary signals, where each signal initially has a value of 0. There are n different pings made to these signals, changing their values from 0 to 1. The i-th ping affects the signal at index ping[i].
After each ping, the processor sorts the array by performing sweeps from left to right, swapping adjacent elements where signal[j] = 1 and signal[j + 1] = 0. The processor stops when no swaps are made in a sweep.
Determine the number of sweeps required after each ping to sort the array.
Note: Each signal is only pinged once.
Complete the function getRequiredSweeps. It accepts the integer array ping, where each value identifies the signal called by that ping, and returns an integer array containing the number of sweeps required after each ping.
Function
getRequiredSweeps(ping: int[]) → int[]Examples
Example 1
ping = [1, 2, 4, 3]return = [2, 3, 3, 1]Here, n = 4. The sweep counts after each ping are:
| Ping | Operations required to process signals | Signal after the ping |
|---|---|---|
| 1 | One sweep sorts the array into [0, 0, 0, 1]. One additional sweep is run with no swaps, for a total of 2 sweeps. | [1, 0, 0, 0] |
| 2 | Two sweeps sort the array. One additional sweep is run with no swaps, for a total of 3 sweeps. | [1, 1, 0, 0] |
| 3 | Two sweeps sort the array. One additional sweep is run with no swaps, for a total of 3 sweeps. | [1, 1, 0, 1] |
| 4 | The signal is already sorted, so one sweep with no swaps is sufficient. | [1, 1, 1, 1] |
Therefore, return [2, 3, 3, 1].