n charged particles move along a single straight line, given in left-to-right position order. Each particle is one nonzero integer: its sign is the direction of travel (positive = moving right, negative = moving left) and its absolute value is its charge magnitude. All particles move at the same speed.
Two particles annihilate only when a right-moving particle is immediately followed (among still-surviving particles) by a left-moving particle. In such a collision the particle with the strictly larger magnitude survives and destroys the other; if the magnitudes are equal, both are destroyed. A surviving right-moving particle may then collide with the next surviving left-moving particle, and so on. Same-direction particles never collide.
After all collisions finish, report how many particles were destroyed in total (that is, n minus the number of survivors).
Line 1: an integer n.
Line 2: n space-separated nonzero integers, the signed charges in left-to-right order.
A single integer: the total number of destroyed particles.
Example 1
Input
3 5 10 -5
Expected
1
Explanation
The right-moving 10 meets the left-moving -5; 10 is larger, so -5 is destroyed. The 5 never collides. One particle is destroyed.
Example 2
Input
2 8 -8
Expected
2
Explanation
Equal magnitudes moving toward each other annihilate both. Two particles are destroyed.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →