FastPrep
Problem · Array

Signal Pings

Learn this problem
● MediumVisa logoVisaNEW GRADOA

Problem 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:

Sweep counts for each ping
PingOperations required to process signalsSignal after the ping
1One 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]
2Two sweeps sort the array. One additional sweep is run with no swaps, for a total of 3 sweeps.[1, 1, 0, 0]
3Two sweeps sort the array. One additional sweep is run with no swaps, for a total of 3 sweeps.[1, 1, 0, 1]
4The signal is already sorted, so one sweep with no swaps is sufficient.[1, 1, 1, 1]

Therefore, return [2, 3, 3, 1].

More Visa problems

drafts saved locally
public int[] getRequiredSweeps(int[] ping) {
  // write your code here
}
ping[1, 2, 4, 3]
expected[2, 3, 3, 1]
checking account