3782. Last Remaining Integer After Alternating Deletion Operations
Description
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
Solutions
Solution 1
Thinking
\(n\) can be \(10^{15}\), so we cannot simulate the deletions. The process is a Josephus variant that alternately drops every other number from the left then the right. We keep the first term and common difference of the surviving arithmetic progression until one value remains.
1 | |
1 | |
1 | |
1 | |