390. Elimination Game – Leetcode Solutions

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

class Solution:
    def lastRemaining(self, n: int) -> int:
        # Initialize variables
        head = 1          # Starting element
        step = 1          # Initial step size
        left_to_right = True  # Start elimination from left-to-right
        remaining = n     # Number of elements remaining

        # Loop until only one element remains
        while remaining > 1:
            # If we're moving left-to-right, or if there is an odd number of remaining elements
            # (in right-to-left, odd remaining means the head will shift)
            if left_to_right or remaining % 2 == 1:
                head += step
            
            # Double the step for the next round as every other element is removed
            step *= 2
            # Toggle the direction
            left_to_right = not left_to_right
            # Halve the remaining elements as half are removed in each round
            remaining //= 2

        # The last remaining number is stored in head
        return head

class Solution {
public:
    int lastRemaining(int n) {
        // Initialize variables:
        // - 'left_to_right' indicates the current direction of elimination.
        // - 'remaining' keeps track of the number of elements still in the list.
        // - 'step' is the interval between remaining elements after each round.
        // - 'head' keeps track of the starting element in the list after each round.
        bool left_to_right = true;
        int remaining = n;
        int step = 1;
        int head = 1;
        
        // Loop until only one element remains
        while (remaining > 1) {
            // If we are moving left to right or if remaining elements are odd,
            // the head will move forward by 'step' amount.
            if (left_to_right || remaining % 2 == 1) {
                head += step;
            }
            
            // After each round, the number of remaining elements is halved,
            // and the step size doubles.
            remaining /= 2;
            step *= 2;
            left_to_right = !left_to_right;  // Alternate direction
        }
        
        // The last remaining element is stored in 'head'
        return head;
    }
};

var lastRemaining = function(n) {
    // Initialize the first number in the sequence
    let first = 1;
    
    // Initialize the step size, which doubles every round
    let step = 1;
    
    // Track whether we are moving left to right (true) or right to left (false)
    let leftToRight = true;
    
    // Continue until there is only one element remaining
    while (n > 1) {
        // If moving left to right or if n is odd, update `first`
        if (leftToRight || n % 2 === 1) {
            first += step;
        }
        
        // Move to the next round with a doubled step and switch direction
        step *= 2;
        n = Math.floor(n / 2);
        leftToRight = !leftToRight;
    }
    
    // `first` will hold the last remaining number
    return first;
};

class Solution {
    public int lastRemaining(int n) {
        // Initialize variables for the first element, step size, and number of elements left
        int start = 1;       // Start of the list in each iteration
        int step = 1;        // Step size between elements after each round
        int remaining = n;   // Number of remaining elements in the list
        boolean leftToRight = true; // Direction flag, starts with left-to-right pass

        // Continue the elimination until only one element remains
        while (remaining > 1) {
            // If we're moving from left-to-right, or if the remaining count is odd when moving right-to-left,
            // we must update the starting element because the first element is always removed.
            if (leftToRight || remaining % 2 == 1) {
                start += step;
            }

            // Update remaining number of elements and step size
            remaining /= 2;
            step *= 2;

            // Toggle the direction for the next pass
            leftToRight = !leftToRight;
        }

        // 'start' is the last remaining element
        return start;
    }
}