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?
spacecrafts = 10, the output should be
surviveIt(spacecrafts) = 8.
Initially, there are
10 spacecrafts. After your first attack, only half of them will survive:
After your second attack, only
2 spacecrafts will remain:
4 will be vaporized, so spacecraft
8 will be the only one left.
- [time limit] 4000ms (js)
[input] integer spacecrafts
1 ≤ spacecrafts ≤ 109.
The number of the last spacecraft to survive your attacks.
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.
surviveIt = n => 1 << Math.log2(n)