ปัญหา
กำหนด start และ end หาจำนวน operation น้อยที่สุดเพื่อแปลง start → end ด้วย operation 2 อย่าง:
1. ลดลง 1 (decrement)
2. คูณ 2 (multiply)
ตัวอย่าง: start=2, end=7 → 3 operations
2 ×2 = 4, ×2 = 8, -1 = 7
วิธีแก้: Greedy จาก Target ย้อนกลับ (Reverse Thinking)
แทนที่จะคิดจาก start → end (branch factor 2) ให้คิดจาก end → start (deterministic)
อัลกอริทึม
- ถ้า end ≤ start: คืนค่า ans + (start - end) (แค่ลบ 1 ซ้ำ)
- ถ้า end เป็นคี่: end += 1 (ย้อนกลับของ -1), ans++
- ถ้า end เป็นคู่: end //= 2 (ย้อนกลับของ ×2), ans++
- ซ้ำจนกว่า end ≤ start
ทำไมทำงานได้?
- คูณ 2 → ย้อนกลับคือ หาร 2 (เฉพาะเลขคู่)
- ลบ 1 → ย้อนกลับคือ บวก 1
- เลขคี่ ต้องบวก 1 ก่อนจึงจะหาร 2 ได้
- Greedy optimal เพราะ operation ย้อนกลับมีทางเลือกเดียวเสมอ
โค้ด Python
class Solution:
def solve(self, start, end):
ans = 0
while True:
if end <= start:
return ans + start - end
elif end % 2 == 1: # odd
end += 1
ans += 1
else: # even
end //= 2
ans += 1
# ทดสอบ
ob = Solution()
print(ob.solve(2, 7)) # 3
print(ob.solve(5, 8)) # 2 (5→10→9→8? ไม่ 5×2=10 -1-1=8 → 3 ops. แต่ 5+1+1+1=8 → 3. Wait: 5*2=10, 10-1-1=8 = 3 ops)
print(ob.solve(3, 10)) # 3 (3→6→5→10? 3*2=6, 6-1=5, 5*2=10 = 3)
print(ob.solve(10, 1)) # 9 (just decrement)
ความซับซ้อน
- Time: O(log end) - end ลดลงครึ่งเรื่อยๆ
- Space: O(1)
LeetCode 991: Broken Calculator
นี่คือโจทย์ "Broken Calculator" - รูปแบบ Greedy ย้อนกลับคลาสสิก
