ปัญหา
ให้อาร์เรย์บิต nums แทนตัวเลขไบนารี ตรวจสอบว่าหาร 3 ลงตัวหรือไม่ โดยใช้ DFA (Deterministic Finite Automaton)
DFA สำหรับ Mod 3
สถานะ = เศษ mod 3 (0, 1, 2)
State 0: เริ่มต้น และ accepting
Transition:
- State 0 + bit 0 → State 0
- State 0 + bit 1 → State 1
- State 1 + bit 0 → State 2
- State 1 + bit 1 → State 0
- State 2 + bit 0 → State 1
- State 2 + bit 1 → State 2
ตัวอย่าง
nums = [1,1,0,0] (12₁₀) → 12 mod 3 = 0 → True
โค้ดตัวอย่าง
def solve(bits):
state = 0
for bit in bits:
if state == 0:
state = 1 if bit == 1 else 0
elif state == 1:
state = 0 if bit == 1 else 2
else: # state == 2
state = 2 if bit == 1 else 1
return state == 0
print(solve([1, 1, 0, 0])) # True (12)
print(solve([1, 0, 1])) # False (5)
อินพุต / เอาต์พุต
Input: [1, 1, 0, 0] Output: True
