Skip to the content

The colliding particles

Problem

Anneliese Brandt, an experimental physicist, switches off the beam of the linear accelerator and needs to know which particles are still alive in the vacuum tube. You get particles, the row in the tube from left to right: nonzero whole numbers (it may be empty). The sign is the direction (positive to the right, negative to the left) and the absolute value is the mass. They all move at the same speed: the only collision is between one moving right and the one right after it, if that one moves left. Two going the same way never catch up, and a -2 followed by a 1 drift apart. In a collision the lighter one disintegrates and the other goes on unchanged; with equal masses, both do. Once one is removed, its neighbors end up side by side and may collide: repeat until no collision is left. Return the survivors in their order, or [] if none are left. With [3, -7, 2, 4, -4]: 3 hits -7 and the 3 disintegrates; 4 and -4 weigh the same and both vanish; the 2 has no one left to hit. You return [-7, 2].

Examples

  • The example

    [3, -7, 2, 4, -4] → [-7, 2]

  • The heavy one eats the light one

    [5, 10, -5] → [5, 10]

  • Equal masses, both vanish

    [8, -8] → []

  • They drift apart and nobody collides

    [-2, -1, 1, 2] → [-2, -1, 1, 2]

  • One collision opens another

    [10, 2, -5] → [10]

  • A single particle

    [4] → [4]

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

Python

def survivors(particles):
    pass

JavaScript

function survivors(particles) {
}
Solve this challenge

It opens in your browser, with the editor and the tests. This challenge is part of the full plan; the O(1) and O(log n) ones are free.

More O(n²) challenges

See all challenges →