Elimination Game Problem


Description

LeetCode Problem 390.

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:

1
2
3
4
5
6
7
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:

1
2
Input: n = 1
Output: 1

Constraints:

  • 1 <= n <= 10^9


Sample C++ Code

Let n be how many numbers left in the array, and direction can be either left->right or right->left.

There are four cases to consider:

  • n is odd and direction is left->right, [1, 2, 3, 4, 5] -> [2, 4], start of the sequence increases
  • n is odd and direction is right->left, [1, 2, 3, 4, 5] -> [2, 4], start of the sequence increases
  • n is even and direction is left->right, [1, 2, 3, 4] -> [2, 4], start of the sequence increases
  • n is even and direction is right->left, [1, 2, 3, 4] -> [1, 3] , start of the sequence is the same as before

We also use diff to keep track of differences between adjacent integers left in the array. Every time we run the algorithm, we count if the start of the sequence increases or not, and if it increases, it increases by diff.

Example:

1
2
3
4
1 2 3 4 5 6 7 8 9 10 11 12 -> diff = 1
  2   4   6   8   10    12 -> start increases by 1, diff = 2
  2       6       10       -> start is the same, diff = 4
          6                -> start increases by 4, this is the Answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution
{
public:
    int lastRemaining(int n)
    {
        int diff = 1, direction = 0, start = 1;
        //direction = 0 means direction is left->right
        //direction = 1 means direction is right->left
        while (n > 1)
        {
            if (n & 1 || direction == 0) {
            	// n is odd or when n is even and direction is left to right
            	// we increase start by diff
                start += diff;
            }
            // number of integers left in the array
            n /= 2;
            // diff is doubled 
            diff *= 2;         
            // flip direction     
            direction = !direction; 
        }
        return start;
    }
};




Related Posts

Elimination Game Problem

LeetCode 390. You have a list arr of all integers...

Permutation Sequence Problem

LeetCode 60. Given n and k, return the kth permutation...

Regular Expression Matching Problem

LeetCode 10. Given an input string s and a pattern...

Pow(x,n) Problem

LeetCode 50. Determine if a 9 x 9 Sudoku board...