Find X-Sum of All K-Long Subarrays I
Real-world version: The Loudest Tracks in Every StretchThe statement here is our own: the same inputs, outputs and technique.
A jukebox log lists what was played, plays[i] being the track number of the i-th play.
The weight of a stretch of plays is worked out like this: tally how often each track turns up in the stretch, then keep the keep tracks with the highest tallies, settling a tie in favour of the higher track number. The weight is the total of each kept track's number times its tally in the stretch. When the stretch holds keep or fewer distinct tracks they are all kept, so its weight is the total of the stretch.
Return an array whose i-th entry is the weight of the stretch of span plays starting at position i.
Examples
Example 1
- Input
- plays = [4, 4, 5, 6, 6, 6], span = 3, keep = 1
- Output
- [8, 6, 12, 18]
Four stretches of three plays. The first tallies track 4 twice against track 5 once and keeps track 4 for 8. The second tallies all three tracks once, so the tie hands it to track 6. The third keeps track 6 with two plays for 12, and the last is three plays of track 6.
Example 2
- Input
- plays = [2, 2, 3, 3], span = 4, keep = 1
- Output
- [6]
One stretch, in which tracks 2 and 3 are both tallied twice. The tie goes to the higher track number, so track 3 is kept for two plays.
Example 3
- Input
- plays = [1, 1, 1, 9], span = 4, keep = 2
- Output
- [12]
The stretch holds only two distinct tracks and both are kept, so the weight is the total of the whole stretch.
Constraints
- 1 <= plays.length <= 50
- 1 <= plays[i] <= 50
- 1 <= keep <= 50
- 1 <= span <= 50
- keep <= span <= plays.length
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def find_x_sum(plays: list[int], span: int, keep: int) -> list[int]:public int[] findXSum(int[] plays, int span, int keep)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's