Watch 7 video solutions for Last Remaining Integer After Alternating Deletion Operations, a hard level problem involving Math, Recursion. This walkthrough by CodeWithMeGuys has 272 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
Return the last remaining integer.
Example 1:
Input: n = 8
Output: 3
Explanation:
[1, 2, 3, 4, 5, 6, 7, 8] in a sequence.[1, 2, 3, 4, 5, 6, 7, 8]. The remaining integers are [1, 3, 5, 7].[1, 3, 5, 7]. The remaining integers are [3, 7].[3, 7]. The remaining integer is [3].Example 2:
Input: n = 5
Output: 1
Explanation:
[1, 2, 3, 4, 5] in a sequence.[1, 2, 3, 4, 5]. The remaining integers are [1, 3, 5].[1, 3, 5]. The remaining integers are [1, 5].[1, 5]. The remaining integer is [1].Example 3:
Input: n = 1
Output: 1
Explanation:
[1] in a sequence.
Constraints:
1 <= n <= 1015Problem 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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation with List | O(n^2) | O(n) | Useful for understanding the process or verifying small inputs |
| Mathematical Recursion / Head-Step Tracking | O(log n) | O(1) | Best solution for large n and typical interview expectations |