Broken Calculator: Tối Ưu Số Phép Toán (×2, -1) Từ X Đến Y

Đề bài: Máy tính hỏng chỉ làm được 2 phép: ×2 (Double) hoặc -1 (Decrement). Từ X ban đầu, tìm số phép tối thiểu để ra Y.

Ví dụ: X=5, Y=8 → 5-1=4, 4×2=8 → 2 phép.

Quan sát quan trọng: Làm ngược từ Y về X

Thay vì từ X → Y (nhiều lựa chọn), làm ngược Y → X:

• Nếu Y ≤ X: chỉ có thể Decrement → cần X - Y phép.
• Nếu Y > X:
  • Y chẵn: phép ngược của ×2 là ÷2 → Y = Y/2, 1 phép.
  • Y lẻ: không thể ÷2 → phải làm ngược Decrement là +1 → Y = Y+1, 1 phép (sau đó Y chẵn, sẽ ÷2).

Tổng phép = số bước lặp + X - Y (khi Y ≤ X).

Code Python

class Solution:
    def brokenCalc(self, X: int, Y: int) -> int:
        steps = 0
        while Y > X:
            if Y % 2 == 0:
                Y //= 2
            else:
                Y += 1
            steps += 1
        return steps + (X - Y)

# Test
ob = Solution()
print(ob.brokenCalc(5, 8))    # 2
print(ob.brokenCalc(3, 10))   # 3 (3→6→5→10 or 3→2→4→5→10? Wait: 3→6×2, 6→5-1, 5→10×2 = 3 steps)
print(ob.brokenCalc(10, 1))   # 9 (chỉ decrement)
print(ob.brokenCalc(1, 1000000000))  # Large test

Chứng minh tính đúng đắn (Greedy)

• Khi Y > X, mục tiêu giảm Y nhanh nhất.
• ÷2 giảm nhanh hơn +1 → ưu tiên ÷2 khi Y chẵn.
• Khi Y lẻ, buộc phải +1 để biến thành chẵn (vì không thể ÷2 số lẻ).
• Greedy choice này tối ưu vì mỗi bước giảm "khoảng cách" đến X tối đa.

Phân tích

• Time: O(log Y) (Y giảm ít nhất một nửa mỗi 2 bước).
• Space: O(1).

Kết luận

Tư duy ngược (reverse engineering) biến bài toán khó thành greedy đơn giản. Pattern phổ biến: khi operation không đối xứng, hãy xem ngược từ target.