Integer replacement

Dynamic Programming Greedy Bit Manipulation Memoization

37.2% acceptance

Jan 12, 2026

1433

485

Given a positive integer n, you can apply one of the following operations: If n is even, replace n with n / 2. If n is odd, replace n with either n + 1 or n - 1. Return the minimum number of operations needed for n to become 1.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn integer_replacement(n: i32) -> i32 {
    let mut n = n as i64;
    let mut count = 0;
    
    while n != 1 {
      if n % 2 == 0 {
        n /= 2;
      } else if n == 3 || (n >> 1) & 1 == 0 {
        n -= 1;
      } else {
        n += 1;
      }
      count += 1;
    }
    
    count
  }
}