मान लीजिए हमारे पास एक सरणी n है जो किसी संख्या के बाइनरी प्रतिनिधित्व को दर्शाती है। हमें डिटरमिनिस्टिक फाइनाइट ऑटोमेटा (DFA) का उपयोग करके जांचना है कि इसका बाइनरी प्रतिनिधित्व 3 से विभाज्य है या नहीं।
उदाहरण के लिए, यदि n = [1, 1, 0, 0] (12 का बाइनरी) है, तो आउटपुट True होगा।
हल करने का तरीका
हम DFA इस तरह बना सकते हैं: जब कोई संख्या 3 से विभाज्य होती है तो शेषफल 0 होगा, यदि नहीं तो शेषफल 1 या 2 होगा। इन तीन शेषफलों के लिए तीन अवस्थाएं हैं। प्रारंभिक अवस्था अंतिम अवस्था भी है क्योंकि जब शेषफल 0 होता है तो इसका मतलब संख्या विभाज्य है।
- dfa_state := 0
- प्रत्येक बिट के लिए:
- यदि dfa_state 0 है और बिट 1 है, तो dfa_state := 1
- यदि dfa_state 1 है और बिट 0 है, तो dfa_state := 2; यदि बिट 1 है तो dfa_state := 0
- यदि dfa_state 2 है और बिट 0 है, तो dfa_state := 1
- यदि dfa_state 0 है तो True लौटाएं, अन्यथा False
उदाहरण
def solve(nums):
dfa_state = 0
for i in range(len(nums)):
digit = nums[i]
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
if dfa_state == 0:
return True
return False
n = [1, 1, 0, 0]
print(solve(n))
इनपुट
[1, 1, 0, 0]
आउटपुट
True
