Last remaining integer after alternating deletion operations

Math Recursion

48.6% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn last_integer(n: i64) -> i64 {
    let mut first = 1i64;
    let mut step = 1i64;
    let mut count = n;
    let mut left = true;
    while count > 1 {
      if left {
        // keep 0th, 2nd, ... from left
        step *= 2;
        count = (count + 1) / 2;
      } else {
        // keep 0th, 2nd, ... from right
        if count % 2 == 0 { first += step; }
        step *= 2;
        count = (count + 1) / 2;
      }
      left = !left;
    }
    first
  }
}