397. Integer Replacement

class Solution {
public:
    int integerReplacement(int n) {
        return replace_integer(n);
    }

private:
    unordered_map<long, int> replace_times{{1, 0}};

    int replace_integer(long n) {
        if (replace_times.find(n) != replace_times.end()) {
            return replace_times[n];
        }

        int result = 0;
        if ((n & 1) == 0) {
            result = 1 + replace_integer(n >> 1);
        } else {
            result = 2 + min(replace_integer((n + 1) >> 1), replace_integer((n - 1) >> 1));
        }

        replace_times[n] = result;
        return result;
    }
};

// Goal:
// Reduce n to 1 with the minimum number of operations.
//
// Observations:
// 1) If n is even, the only valid move is n = n / 2.
// 2) If n is odd, we must choose between n + 1 and n - 1.
//    The key idea is to make n divisible by a higher power of 2 as soon as possible,
//    so that we can apply consecutive right shifts.
//
// Greedy strategy for odd n (n > 1):
// - Look at the last two bits of n:
//   * If n % 4 == 1 (binary ends with '01'):
//       n - 1 turns '01' into '00', enabling an immediate division by 2.
//   * If n % 4 == 3 (binary ends with '11'):
//       n + 1 produces a carry, typically creating more trailing zeros,
//       which leads to more divisions by 2 afterward.
// - Special case: n == 3
//     Although 3 % 4 == 3, using n - 1 is optimal:
//     3 -> 2 -> 1 (2 steps) is better than 3 -> 4 -> 2 -> 1 (3 steps).
class Solution {
public:
    int integerReplacement(int n) {
        int replace_count = 0;
        long number = n;
        while (number > 1) {
            if ((number & 1) == 0) {
                number >>= 1;
            } else {
                if (number == 3 || (number & 3) == 1) {
                    --number;
                } else {
                    ++number;
                }
            }

            ++replace_count;
        }

        return replace_count;
    }
};