একটি বাইনারি অ্যারে n দেওয়া আছে (যা একটি সংখ্যার বাইনারি রিপ্রেজেন্টেশন)। Deterministic Finite Automata (DFA) ব্যবহার করে এটি ৩ দিয়ে বিভাজ্য কিনা যাচাই করতে হবে।
DFA স্টেট ডায়াগ্রাম
৩ স্টেট: ০ (রিমেইন্ডার ০), ১ (রিমেইন্ডার ১), ২ (রিমেইন্ডার ২)। স্টেট ০ হলো ফাইনাল স্টেট।
ট্রানজিশন
- স্টেট ০: ইনপুট ১ -> স্টেট ১, ইনপুট ০ -> স্টেট ০।
- স্টেট ১: ইনপুট ০ -> স্টেট ২, ইনপুট ১ -> স্টেট ০।
- স্টেট ২: ইনপুট ০ -> স্টেট ১, ইনপুট ১ -> স্টেট ২।
উদাহরণ
ইনপুট: n = [1, 1, 0, 0] (১২-এর বাইনারি)
আউটপুট: True
উদাহরণ কোড
def solve(nums):
dfa_state = 0
for digit in nums:
if dfa_state == 0:
if digit == 1:
dfa_state = 1
elif dfa_state == 1:
if digit == 0:
dfa_state = 2
else:
dfa_state = 0
elif dfa_state == 2:
if digit == 0:
dfa_state = 1
return dfa_state == 0
n = [1, 1, 0, 0]
print(solve(n)) # Output: True
ইনপুট
[1, 1, 0, 0]আউটপুট
True