Codesignal Solution: surviveIt

Original Problem

Your spaceship is carrying the last few people from Earth towards a distant planet that will become the new home of the Earth civilization. You've just gotten a distress signal, and since nothing could possibly go wrong, you've decided to investigate the source of the signal.

Unfortunately, it turns out that the signal was sent by a hostile alien army. Your spaceship is now facing n alien spacecrafts, and it's your duty to destroy them! Luckily, you have an amazing defense system that destroys half of the hostile army at a time by vaporizing all the enemy spacecrafts that are at odd positions.

The system will keep destroying alien ships until there's only one left. What number will this spacecraft have?

Example

For spacecrafts = 10, the output should be
surviveIt(spacecrafts) = 8.

Initially, there are 10 spacecrafts. After your first attack, only half of them will survive: 2, 4, 6, 8 and 10.
After your second attack, only 2 spacecrafts will remain: 4 and 8.
Finally, spacecraft 4 will be vaporized, so spacecraft 8 will be the only one left.

Output/Input

• [time limit] 4000ms (js)

• [input] integer spacecrafts

  Guaranteed constraints:
  1 ≤ spacecrafts ≤ 10⁹.

• [output] integer

  The number of the last spacecraft to survive your attacks.

Solution

This problem is quite similar to the Josephus Problem we solved already. The difference here is that we don't delete circularly but linearly. For the Josephus Problem, we knew that for a number \(n\) being a power of two, every remaining set will also be a power of two (since we always remove the half). When looking at the number in binary, the trick is to move the most significant bit from the left, to the least signifiant position. For example a binary number 0b101001 will become 0b010011.

For this problem, two things are different: We don't work circular, but always start at the beginning plus, we keep the even instead of the odd. When playing the game a few times, the following pattern emerges: 1, 2, 2, 4, 4, 4, 8, 8, ... They are all powers of two. In fact, they are the simply the most significant bit. That means, to solve this problem, all we need to do is calculating the MSB, using an integer log base two. Implemented in JavaScript, this looks like:

surviveIt = n => 1 << Math.log2(n)