[LeetCode] 390. Elimination Game [Need Re-do]

1. Question

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

2. Thoughts

=> Couldn't solve

3. Tips learned

4. My solution

    def lastRemaining(self, n: int) -> int:
        if n <= 2:
            return n
        if n == 3:
            return 2
        all = set()

        if (n // 2) % 2 == 0:
            index = 1
        else:
            index = 3
        while index < n:
            all.add(index)
            index += 4

        to_right = 1
        while len(all) != 1:
            if to_right or len(all) % 2 == 1:
                start = 0
            else:
                start = 1

            i = 0
            temp_list = sorted(all)
            for var in temp_list:
                if i % 2 == start:
                    all.remove(var)
                i += 1

            to_right = (to_right + 1) % 2

        return list(all)[0] + 1

Memory Limit Exceeded
3375/3377 cases passed (N/A)
Testcase
100000000
Expected Answer
32896342

5. AI Solution and Improvements

To solve this problem efficiently without hitting a time limit, you can adopt a mathematical approach instead of simulating the entire process, which can become inefficient for large values of n. The idea is to observe patterns and rules that emerge as you remove elements from the array according to the algorithm's rules.

Here's a more efficient strategy:

1. Observation of the Pattern: Notice how with each complete pass (left to right and right to left), the starting number, the difference between numbers, and the count of the numbers change in a predictable way.
2. Left to Right Removal: Every time you remove numbers from left to right, you effectively remove the first number in the current list, and every second number remains. This operation halves the list and changes the starting number and step between remaining numbers.
3. Right to Left Removal: This operation has a similar effect but only changes the starting number if the count of numbers before removal is odd.
4. Keep Track of the Start, Step, and Length: Instead of explicitly removing numbers, keep track of the starting number, the step between consecutive numbers, and the remaining length of the list. Adjust these values according to the rules derived from observations.

Here's how you could implement this approach:

• Start is initially 1 (since the list starts at 1).
• Step is initially 1 (since the initial difference between numbers is 1).
• Length is initially n.
• After each left-to-right pass, the Start increases by Step, and Step doubles.
• After each right-to-left pass, Start may or may not change based on the remaining length of the list, and Step doubles.

This process continues until the remaining length of the list is 1.

Let's implement this improved solution:

def lastRemaining(n: int) -> int:
    start = 1  # The first number in the list.
    step = 1  # The difference between consecutive numbers in the list.
    remaining = n  # The remaining count of numbers in the list.
    left_to_right = True  # Direction of removal.

    while remaining > 1:
        if left_to_right or remaining % 2 == 1:
            # If we are moving left to right or the count of remaining numbers is odd,
            # the start changes because the first or last (in case of odd during right to left)
            # number will be removed.
            start += step
        # After each pass (both directions), the difference between the remaining numbers doubles.
        step *= 2
        # Halve the count of remaining numbers after each pass.
        remaining //= 2
        # Toggle the direction for the next pass.
        left_to_right = not left_to_right

    return start

This solution works in (O(\log n)) time complexity, which is significantly faster than the simulated approach, especially for large n. It avoids the time limit issue by not explicitly removing each element and instead mathematically calculating the position of the remaining number after all removals have been performed.