Integer Replacement

 

This is a problem I brought along to the WICSxACM Technical Interview Prep workshop on 13 January 2020. It is also available at bit.ly/integer-replacement.

Problem Description

Source: LeetCode 397

Given a positive integer \(n\), you can perform 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\)

What is the minimum number of replacements needed for \(n\) to become \(1\)?

Hints

  1. The initial temptation is to go for a fancy, math-based \(O(1)\) solution, but there are more general approaches that will increase your chances of actually coming up with a solution. What are some other approaches you can think of?
  2. How can you think of the problem as a graph? (For this workshop, I know there have been quite a few other graph problems, so this will be fresh in your mind.)

Solution

I have implemented one possible solution to the problem. I chose to use C++ because it is the language I prefer to use in interviews. Python makes things too easy. IMHO interviewers will want to see your implementation skills, and C++ is the way to do that. Of course, this will vary on a case-by-case basis. Some companies mainly use Python and will want to interview you in Python, for instance.

Approach 1: BFS

This solution was suggested in the Hints. The idea is to think of the numbers as a graph, where each number is a node and there are edges connecting each node \(x\) to \(x/2\) if \(x\) is even, or to \(x + 1\) and \(x - 1\) if \(x\) is odd. We can then perform a BFS (Breadth-First Search) on the graph to find the length of the shortest path from \(n\) to \(1\).

  • Time complexity: \(O(n)\) – we can only encounter numbers in the range \([1, 2n]\) since if you reach \(2n\), you wasted a bunch of steps because \(2n\) can just be divided by \(2\) to get \(n\). Since we never visit the same number twice, the time complexity is \(O(2n) = O(n)\)
  • Space complexity: \(O(n)\) – same reason as above.
class Solution {
 public:
  int integerReplacement(int n) {
    // Queue for BFS -- each pair holds a number `x` and the number
    // of steps it is from `n`. we use `long long` to account for the
    // edge case when `n == INT_MAX`. Note that as we pop nodes from
    // and add nodes to this queue, the number of steps gradually
    // increases. Furthermore, note that we are guaranteed to visit all nodes
    // that are `k` steps from `n` before any nodes that are `k + 1` steps
    // from `n`.
    queue<pair<long long, int>> q;

    // Visited set -- holds numbers that have already been encountered.
    // Numbers enter this set when they are first encountered by the
    // algorithm. We do not want to revisit these numbers because we only
    // care about the minimum number of steps to visit them.
    unordered_set<long long> visited;

    // The queue starts with `n` at 0 steps, and `n` is visited to begin with.
    q.push({n, 0});
    visited.insert(n);

    // BFS loop.
    while (!q.empty()) {
      // Retrieve the next `x` and `steps` from the queue.
      long long x;
      int steps;
      tie(x, steps) = q.front();  // See std::tie
      q.pop();

      // We solved the problem -- return the number of steps.
      if (x == 1) return steps;

      if (x % 2 == 0) {
        // If x is even, the only node connected to it will be `x/2`
        if (visited.find(x / 2) == visited.end()) {
          // Make sure to record that `x/2` is visited.
          visited.insert(x / 2);
          // Add `x/2` with one more step than `x`.
          q.push({x / 2, steps + 1});
        }
      } else {
        // Same as above, except we now have `x + 1` and `x - 1`
        if (visited.find(x + 1) == visited.end()) {
          visited.insert(x + 1);
          q.push({x + 1, steps + 1});
        }
        if (visited.find(x - 1) == visited.end()) {
          visited.insert(x - 1);
          q.push({x - 1, steps + 1});
        }
      }
    }

    // If for some reason no solution was found.
    return -1;
  }
};

Alternate Approaches

If you look at the discussions on the original LeetCode problem, you will see references to dynamic programming (DP) and recursion. These certainly work too.