390. Elimination Game

390. Elimination Game

There is a list of sorted integers from 1 to n. 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 right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input:n = 9,1 2 3 4 5 6 7 8 92 4 6 82 66Output:

class Solution { public int lastRemaining(int n) { if(n < 1){ return 0; } if(n==1){ return 1; } int gap = 1; // gap between 2 elements int res = 1; while(gap*2 <= n){ // check if there is next element // from left to right, always delete the first element res += gap; // after each run through, gap *=2 gap *= 2; // from right to left if(gap*2 <= n){ // check if 1st element needs to be deleted if((n/gap) % 2 == 1){ // only when odd numbers of elements left, we need to delete the 1st element res += gap; } gap *= 2; } } return

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。