Skip to main content
Talentd

Last Remaining Integer After Alternating Deletion Operations - Solution & Explanation

HardMathRecursion3 min read
Practice this problem

Problem Statement

You are given an integer n.

We write the integers from 1 to n in a sequence from left to right. Then, alternately apply the following two operations until only one integer remains, starting with operation 1:

  • Operation 1: Starting from the left, delete every second number.
  • Operation 2: Starting from the right, delete every second number.

Return the last remaining integer.

 

Example 1:

Input: n = 8

Output: 3

Explanation:

  • Write [1, 2, 3, 4, 5, 6, 7, 8] in a sequence.
  • Starting from the left, we delete every second number: [1, 2, 3, 4, 5, 6, 7, 8]. The remaining integers are [1, 3, 5, 7].
  • Starting from the right, we delete every second number: [1, 3, 5, 7]. The remaining integers are [3, 7].
  • Starting from the left, we delete every second number: [3, 7]. The remaining integer is [3].

Example 2:

Input: n = 5

Output: 1

Explanation:

  • Write [1, 2, 3, 4, 5] in a sequence.
  • Starting from the left, we delete every second number: [1, 2, 3, 4, 5]. The remaining integers are [1, 3, 5].
  • Starting from the right, we delete every second number: [1, 3, 5]. The remaining integers are [1, 5].
  • Starting from the left, we delete every second number: [1, 5]. The remaining integer is [1].

Example 3:

Input: n = 1

Output: 1

Explanation:

  • Write [1] in a sequence.
  • The last remaining integer is 1.

 

Constraints:

  • 1 <= n <= 1015

Approach Overview

Problem Overview: You start with integers from 1 to n. In the first pass, delete every second number from left to right. In the next pass, delete every second number from right to left. Continue alternating directions until only one number remains. Return that final integer.

Approach 1: Direct Simulation (O(n^2) time, O(n) space)

The straightforward method simulates the process using a list containing 1..n. Iterate through the array and remove every second element. After each pass, reverse the direction of traversal and repeat the deletion step. Because element removals shift the array repeatedly, each round becomes expensive. For large n, this approach quickly degrades to roughly O(n^2) time while storing the sequence requires O(n) space.

Approach 2: Mathematical Recursion / Elimination Game (O(log n) time, O(1) space)

The key insight is that you never need to store the entire sequence. Track only four values: the current head (first remaining number), the step size between remaining elements, the number of elements remaining, and the direction of deletion. When deleting from left to right, the head always shifts by step. When deleting from right to left, the head shifts only if the remaining count is odd. After each round, halve the remaining count and double the step because every second element survives. Continue until one element remains.

This transforms the elimination process into a small arithmetic update loop. Each round halves the search space, producing O(log n) time and constant memory. The reasoning relies on patterns in arithmetic progressions, making it a classic math and recursion style problem.

Recommended for interviews: Interviewers expect the mathematical elimination approach. The brute force simulation shows you understand the rules of the process, but the O(log n) head-and-step technique demonstrates pattern recognition and algorithmic optimization. Most strong candidates derive the recurrence or iterative formula during discussion.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Simulation with ListO(n^2)O(n)Useful for understanding the process or verifying small inputs
Mathematical Recursion / Head-Step TrackingO(log n)O(1)Best solution for large n and typical interview expectations

Video Solution

Leetcode 3782 | Last Remaining Integer After Alternating Deletion Operations | Recursion • CodeWithMeGuys • 298 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Last Remaining Integer After Alternating Deletion Operations easy or hard?
The problem is typically rated Hard because the optimal solution requires recognizing a mathematical pattern rather than simulating deletions. Many candidates initially attempt O(n) or O(n^2) simulation before discovering the O(log n) elimination pattern.
Last Remaining Integer After Alternating Deletion Operations Python/Java solution
Most implementations use a loop that updates head, step, remaining count, and direction until only one element remains. The same logic works in Python, Java, C++, and Go with identical O(log n) time complexity.
How to solve Last Remaining Integer After Alternating Deletion Operations in O(log n)?
Track four variables: head, step, remaining elements, and direction. Move the head forward when deleting from the left, and also when deleting from the right if the remaining count is odd. After each pass, divide the remaining count by two and double the step size. Repeat until one number remains.
What is the best approach for Last Remaining Integer After Alternating Deletion Operations?
The optimal solution uses a mathematical elimination pattern that tracks the head element, step size, remaining count, and direction of deletion. Each round halves the number of elements and doubles the step size. This reduces the problem to O(log n) time with O(1) space instead of simulating the entire sequence.
Is Last Remaining Integer After Alternating Deletion Operations asked at Google/Amazon/Meta?
Variants of this elimination pattern appear in interviews at large tech companies including Google, Amazon, and Meta. Interviewers use it to test mathematical reasoning, pattern recognition, and the ability to optimize a brute force simulation.
What data structure is used in Last Remaining Integer After Alternating Deletion Operations?
The optimal solution does not rely on complex data structures. It uses simple integer variables to track the head of the sequence and the step between surviving elements, relying on mathematical properties rather than storing the full array.
What is the time complexity of Last Remaining Integer After Alternating Deletion Operations?
The optimal mathematical approach runs in O(log n) time because each deletion round removes half of the remaining numbers. Only a few variables are updated per round, giving O(1) space complexity.

Ready to solve this problem?

Practice Last Remaining Integer After Alternating Deletion Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer