Leetcode 390: 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

Problem Analysis:

First we can get the trivial solution, we iterate deleting numbers from an array that have number from 1 to n. Finally we get the final remaining number.

class Solution {
public:
    int lastRemaining(int n) {
        vector<int> data(n);
        vector<int> tmp(n);
        int size = n;
        iota(data.begin(), data.end(), 1);
        bool isRight{false};
        while (size > 1) {
            int newSize = size >> 1;
            if (isRight) {
                for (int i = newSize - 1, j = size - 2; i >= 0; --i, j -= 2)
                    tmp[i] = data[j];
            } else {
                for (int i = 0, j = 1; i < newSize; ++i, j += 2)
                    tmp[i] = data[j];
            }
 
            swap(tmp, data);
            isRight = !isRight;
            size = newSize;
        }
        return data.front();
    }
};

Of course, there are some better solutions. First, we can observe that the deleting operation is symmetric, every time we delete half numbers.

Now we define function f(n, left) as the number that n numbers, we first delete from left, then delete from right, …, finally return the last number. So we can get f(n, right), the only different is first delete from right, the return last number should be n+1-f(n, left). As we can regard it as reverse the array 1 … n, and then iterate to delete from left. So f(n, left) = n + 1- f(n, right).

Suppose there is array 1, 2, …, n, after first delete from left, we get subarray 2, 4, …. Then we delete from right, it is similar as we delete the array 1, 2, …, n / 2 from right, f(n/2, right), but number value of array should be 2 * f(n/2, right). So we get another equation: f(n, left) = 2 * f(n/2, right), also f(n, right) = 2 * f(n/2, left).

Finally, We can conclude the general equation f(n, left) = n + 1 -f(n, right) = n + 1 – 2 * f(n/2, left). As first time n may be odd, so we use n / 2 to eliminate the ambiguity((n+1) / 2 == n/2). So f(n, left) = 2 * (n / 2 + 1-f(n/2, left)).

And we can eliminate the left argument, so f(n) = 2 * (n/2 + 1- f(n/2)).

Solution

class Solution {
public:
    int lastRemaining(int n) {
        return n == 1 ? 1 : 2 * (1 + n / 2 - lastRemaining(n / 2));
    }
};

time complexity is O(logn)

Space complexity is O(1)