Algorithm
Problem Name: 390. Elimination Game
Problem Link: https://leetcode.com/problems/elimination-game/
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
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const lastRemaining = function(n) {
let left = true
let remaining = n
let step = 1
let head = 1
while (remaining > 1) {
if (left || remaining % 2 === 1) {
head = head + step
}
remaining = remaining >> 1
step = step * 2
left = !left
}
return head
}
Input
n = 9
Output
6
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def lastRemaining(self, n):
head, left, step, remaining = 1, 1, 1, n
while remaining > 1:
if left or remaining % 2: head += step
left = 1 - left
step *= 2
remaining //= 2
return head
Input
n = 1
Output
1