Thay thế số nguyên (Integer Replacement) trong C++

Mô tả bài toán

Cho số nguyên dương n. Mỗi bước: nếu chẵn → n/=2; nếu lẻ → n+1 hoặc n-1. Tìm số bước tối thiểu để n về 1.

Ví dụ: 7 → 4 bước (7→8→4→2→1 hoặc 7→6→3→2→1).

Giải thuật Tham lam dựa trên bit

• Nếu chẵn: dịch phải 1 bit.
• Nếu lẻ:
  • Nếu n == 3 hoặc bit thứ 2 (từ LSB) là 0 (tức (n>>1)&1 == 0) → n--.
  • Ngược lại → n++ (để tạo ra nhiều bit 0 liên tiếp hơn, giảm nhanh hơn).

Lý do: n+1 thường tạo ra nhiều trailing zeros hơn, cho phép chia 2 nhiều lần liên tiếp.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;
using lli = long long;

class Solution {
public:
    int integerReplacement(int x) {
        lli n = x;
        int steps = 0;
        while (n > 1) {
            if ((n & 1) == 0) n >>= 1;
            else if (n == 3 || ((n >> 1) & 1) == 0) n--;
            else n++;
            steps++;
        }
        return steps;
    }
};

int main() {
    Solution ob;
    cout << ob.integerReplacement(7); // 4
    return 0;
}

Độ phức tạp

• Thời gian: O(log n) (số bit).
• Không gian: O(1).