390. Elimination Game #

Problem #

You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:

• Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
• Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
• Keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Given the integer n, return the last number that remains in arr.

Example 1:

Input: n = 9
Output: 6
Explanation:
arr = [1, 2,3, 4,5, 6,7, 8,9]
arr = [2,4, 6,8]
arr = [2, 6]
arr = [6]

Example 2:

Input: n = 1
Output: 1

Constraints:

• 1 <= n <= 109

Problem Summary #

The list arr consists of all integers in the range [1, n], sorted in strictly increasing order. Please apply the following algorithm to arr:

• From left to right, delete the first number, then delete every other number until reaching the end of the list.
• Repeat the step above, but this time from right to left. That is, delete the rightmost number, then delete every other remaining number.
• Keep repeating these two steps, alternating from left to right and from right to left, until only one number remains.

Given the integer n, return the last remaining number in arr.

Solution Approach #

• Simulation problem. According to the problem statement, the first round deletes numbers from left to right, and the second round deletes numbers from right to left. The problem asks for the last remaining number, so during the simulation there is no need to actually delete elements. You only need to mark the starting element, the step size of the current round, and the direction. When only one element remains, it is the answer.

Code #

package leetcode

func lastRemaining(n int) int {
	start, dir, step := 1, true, 1
	for n > 1 {
		if dir { // forward
			start += step
		} else { // backward
			if n%2 == 1 {
				start += step
			}
		}
		dir = !dir
		n >>= 1
		step <<= 1
	}
	return start
}