Broken Calculator: เครื่องคิดเลขเสีย (Double/Decrement) หา operations น้อยที่สุด

โจทย์

เครื่องคิดเลขเสีย มี 2 ปุ่ม:

• Double: คูณ 2
• Decrement: ลด 1

เริ่มที่ X ต้องการไป Y หา operations น้อยที่สุด

ตัวอย่าง: X=5, Y=8 → 2 ops: 5→4 (dec), 4→8 (double)

ข้อสังเกตสำคัญ: ย้อนกลับ (Reverse Thinking)

แทนที่จะคิด X→Y (branch factor 2) ให้คิด Y→X (branch factor 1 หรือ 2):

• ถ้า Y เป็นเลขคู่: ย้อน Double ได้ → Y = Y/2
• ถ้า Y เป็นเลขคี่: ย้อน Double ไม่ได้ ต้องย้อน Decrement → Y = Y+1
• ทำซ้ำจน Y ≤ X
• Operations ที่เหลือ = X - Y (แค่ Decrement)

การติดตั้ง (Python Implementation)

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

# ทดสอบ
ob = Solution()
print(ob.brokenCalc(5, 8))    # 2
print(ob.brokenCalc(3, 10))   # 3 (3→6→5→10)
print(ob.brokenCalc(10, 1))   # 9 (แค่ decrement)
print(ob.brokenCalc(1, 1000000000))  # Large test

Output

2
3
9
... (คำตอบสำหรับ large test)

การวิเคราะห์ตัวอย่าง X=5, Y=8

Y=8 > 5, even → Y=4, ops=1
Y=4 ≤ 5, stop
Remaining: X-Y = 5-4 = 1
Total: 1 + 1 = 2 ops
Path: 5 → 4 (dec) → 8 (double)

ทำไม Reverse Greedy ถูกต้อง?

• Double (×2) เป็น operation "รุนแรง" เปลี่ยนค่ามาก → ควรทำทีหลัง (forward) / ทีแรก (reverse)
• Decrement (±1) เป็น operation "อ่อน" → ทำทีหลัง (forward) / ทีหลัง (reverse)
• Reverse greedy เลือกการย้อน Double ทุกครั้งที่ทำได้ (Y even) ซึ่งเป็น optimal

Complexity

• Time: O(log Y) - Y ลดลงครึ่งหนึ่งทุก 1-2 steps
• Space: O(1)

สรุป

Broken Calculator เป็นโจทย์ Greytic แบบ Reverse Thinking: คิดย้อนกลับจาก Y ไป X ใช้ parity ของ Y 决定 operation ย้อนกลับ เร็วและ optimal

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ