3782. Last Remaining Integer After Alternating Deletion Operations Hard

1/**
2 * [3782] Last Remaining Integer After Alternating Deletion Operations
3 *
4 * You are given an integer n.
5 * 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:
6 * 
7 * 	Operation 1: Starting from the left, delete every second number.
8 * 	Operation 2: Starting from the right, delete every second number.
9 * 
10 * Return the last remaining integer.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block">
14 * Input: <span class="example-io">n = 8</span>
15 * Output: <span class="example-io">3</span>
16 * Explanation:
17 * 
18 * 	Write [1, 2, 3, 4, 5, 6, 7, 8] in a sequence.
19 * 	Starting from the left, we delete every second number: [1, <u>2</u>, 3, <u>4</u>, 5, <u>6</u>, 7, <u>8</u>]. The remaining integers are [1, 3, 5, 7].
20 * 	Starting from the right, we delete every second number: [<u>1</u>, 3, <u>5</u>, 7]. The remaining integers are [3, 7].
21 * 	Starting from the left, we delete every second number: [3, <u>7</u>]. The remaining integer is [3].
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">n = 5</span>
26 * Output: <span class="example-io">1</span>
27 * Explanation:
28 * 
29 * 	Write [1, 2, 3, 4, 5] in a sequence.
30 * 	Starting from the left, we delete every second number: [1, <u>2</u>, 3, <u>4</u>, 5]. The remaining integers are [1, 3, 5].
31 * 	Starting from the right, we delete every second number: [1, <u>3</u>, 5]. The remaining integers are [1, 5].
32 * 	Starting from the left, we delete every second number: [1, <u>5</u>]. The remaining integer is [1].
33 * </div>
34 * <strong class="example">Example 3:
35 * <div class="example-block">
36 * Input: <span class="example-io">n = 1</span>
37 * Output: <span class="example-io">1</span>
38 * Explanation:
39 * 
40 * 	Write [1] in a sequence.
41 * 	The last remaining integer is 1.
42 * </div>
43 *  
44 * Constraints:
45 * 
46 * 	1 <= n <= 10^15
47 * 
48 */
49pub struct Solution {}
50
51// problem: https://leetcode.com/problems/last-remaining-integer-after-alternating-deletion-operations/
52// discuss: https://leetcode.com/problems/last-remaining-integer-after-alternating-deletion-operations/discuss/?currentPage=1&orderBy=most_votes&query=
53
54// submission codes start here
55
56impl Solution {
57    pub fn last_integer(n: i64) -> i64 {
58        
59    }
60}
61
62// submission codes end
63
64#[cfg(test)]
65mod tests {
66    use super::*;
67
68    #[test]
69    fn test_3782() {
70    }
71}
72