3782. Last Remaining Integer After Alternating Deletion Operations
Hard46.3% acceptance
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].