Integer Replacement

Problem

Given a positive integer n, you can apply one of the following operations:

1. If n is even, replace n with n / 2.
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.

Examples

Example 1:

Input: n = 8
Output: 3
Explanation: 8 -> 4 -> 2 -> 1

Example 2:

Input: n = 7
Output: 4
Explanation:  7 -> 8 -> 4 -> 2 -> 1
or 7 -> 6 -> 3 -> 2 -> 1

Example 3:

Input: n = 4
Output: 2

Solution

Method 1 – Greedy with Recursion and Memoization

Intuition

The problem can be solved by recursively reducing n to 1, always choosing the operation that leads to the minimum steps. For even numbers, divide by 2. For odd numbers, try both n+1 and n-1 and pick the minimum. Memoization avoids redundant calculations.

Approach

1. If n is 1, return 0 (base case).
2. If n is even, recursively call with n/2.
3. If n is odd, recursively call with both n+1 and n-1, take the minimum.
4. Use a cache (memoization) to store results for each n to avoid recomputation.
5. Return the minimum number of steps.

Code

C++

class Solution {
  unordered_map<long, int> memo;
public:
  int integerReplacement(int n) {
    return helper(n);
  }
  int helper(long n) {
    if (n == 1) return 0;
    if (memo.count(n)) return memo[n];
    int ans;
    if (n % 2 == 0) {
      ans = 1 + helper(n / 2);
    } else {
      ans = 1 + min(helper(n + 1), helper(n - 1));
    }
    memo[n] = ans;
    return ans;
  }
};

Go

type Solution struct {
  memo map[int]int
}

func (s *Solution) integerReplacement(n int) int {
  if s.memo == nil {
    s.memo = make(map[int]int)
  }
  if n == 1 {
    return 0
  }
  if v, ok := s.memo[n]; ok {
    return v
  }
  var ans int
  if n%2 == 0 {
    ans = 1 + s.integerReplacement(n/2)
  } else {
    ans = 1 + min(s.integerReplacement(n+1), s.integerReplacement(n-1))
  }
  s.memo[n] = ans
  return ans
}

func min(a, b int) int {
  if a < b {
    return a
  }
  return b
}

Java

class Solution {
  private Map<Long, Integer> memo = new HashMap<>();
  public int integerReplacement(int n) {
    return helper((long)n);
  }
  private int helper(long n) {
    if (n == 1) return 0;
    if (memo.containsKey(n)) return memo.get(n);
    int ans;
    if (n % 2 == 0) {
      ans = 1 + helper(n / 2);
    } else {
      ans = 1 + Math.min(helper(n + 1), helper(n - 1));
    }
    memo.put(n, ans);
    return ans;
  }
}

Kotlin

class Solution {
  private val memo = mutableMapOf<Long, Int>()
  fun integerReplacement(n: Int): Int {
    return helper(n.toLong())
  }
  private fun helper(n: Long): Int {
    if (n == 1L) return 0
    memo[n]?.let { return it }
    val ans = if (n % 2 == 0L) {
      1 + helper(n / 2)
    } else {
      1 + minOf(helper(n + 1), helper(n - 1))
    }
    memo[n] = ans
    return ans
  }
}

Python

class Solution:
  def integerReplacement(self, n: int) -> int:
    memo: dict[int, int] = {}
    def helper(x: int) -> int:
      if x == 1:
        return 0
      if x in memo:
        return memo[x]
      if x % 2 == 0:
        ans = 1 + helper(x // 2)
      else:
        ans = 1 + min(helper(x + 1), helper(x - 1))
      memo[x] = ans
      return ans
    return helper(n)

Rust

use std::collections::HashMap;
impl Solution {
  pub fn integer_replacement(n: i32) -> i32 {
    fn helper(x: i64, memo: &mut HashMap<i64, i32>) -> i32 {
      if x == 1 {
        return 0;
      }
      if let Some(&v) = memo.get(&x) {
        return v;
      }
      let ans = if x % 2 == 0 {
        1 + helper(x / 2, memo)
      } else {
        1 + std::cmp::min(helper(x + 1, memo), helper(x - 1, memo))
      };
      memo.insert(x, ans);
      ans
    }
    helper(n as i64, &mut HashMap::new())
  }
}

Complexity

• Time: O(log n) — Each recursive call reduces n by half or by 1, and memoization ensures each value is computed once.
• Space: O(log n) — For the recursion stack and memoization storage.