5 Best Ways to check if a binary string is a multiple of 3 using DFA in Python

by

💡 Problem Formulation: The challenge involves determining whether a given binary string represents a number that is a multiple of 3. For instance, input "110" (which corresponds to the decimal number 6) should yield a positive confirmation of being a multiple of 3, while "101" (decimal 5) should not.

Method 1: Implementing DFA from Scratch

A deterministic finite automaton (DFA) can be built to simulate the states and transitions based on the input binary string. The DFA will have a set of states representing remainders mod 3, and transitions based on the current bit (0 or 1). When the string is completely processed, if the DFA is in the state that represents the remainder 0, the string is a multiple of 3.

Here’s an example:

def is_multiple_of_three(binary_string):
    state = 0
    for bit in binary_string:
        if bit == '0':
            state = [0, 1, 2][(state << 1) % 3]
        elif bit == '1':
            state = [0, 1, 2][(state << 1 | 1) % 3]
    return state == 0

# Example usage:
print(is_multiple_of_three('110'))

Output:

True

This code snippet declares a function is_multiple_of_three that takes a binary string and computes the final state of the DFA. If the final state is 0, it returns True, indicating the string represents a multiple of 3.

Method 2: Using Transition Table

We can precompute the state transitions into a table to avoid calculations for each bit processed. This method involves using a 2D array where the rows represent the current state and the columns represent the bit read (0 or 1), with each entry showing the next state.

Here’s an example:

transition_table = [
    [0, 1],
    [2, 0],
    [1, 2]
]

def is_multiple_of_three(binary_string):
    state = 0
    for bit in binary_string:
        state = transition_table[state][int(bit)]
    return state == 0

# Example usage:
print(is_multiple_of_three('110'))

Output:

True

The code utilizes a precomputed transition table in a function is_multiple_of_three that iterates over the input binary string. It updates the state using the table and returns True if the final state indicates a multiple of 3.

Method 3: Recursive State Transitions

This method relies on a recursive function to process the binary string, making state transitions for each bit. It uses recursion to simulate the next state based on the current state and the bit. This can be a succinct and elegant approach but may not be as performant for large strings.

Here’s an example:

def is_multiple_of_three(binary_string, state=0):
    if not binary_string:
        return state == 0
    next_bit = int(binary_string[0])
    next_state = [0, 1, 2][(state << 1 | next_bit) % 3]
    return is_multiple_of_three(binary_string[1:], next_state)

# Example usage:
print(is_multiple_of_three('110'))

Output:

True

The recursive function is_multiple_of_three takes a binary string and current state, processes the first bit, and calls itself with the remaining string and new state until the string is empty. It returns True if the final state is 0.

Method 4: Object-Oriented DFA

Using object-oriented programming, one can define a DFA class encapsulating the states, transitions, and validation method. This provides a clear structure and ease of expandability, making the DFA reusable and more maintainable.

Here’s an example:

class DFA:
    def __init__(self):
        self.state = 0

    def transition(self, bit):
        self.state = [0, 1, 2][(self.state << 1 | int(bit)) % 3]

    def is_accepted(self):
        return self.state == 0

def is_multiple_of_three(binary_string):
    dfa = DFA()
    for bit in binary_string:
        dfa.transition(bit)
    return dfa.is_accepted()

# Example usage:
print(is_multiple_of_three('110'))

Output:

True

The DFA class includes a method transition to process input bits and an is_accepted method to check the final state. The function is_multiple_of_three creates an instance of the DFA class and processes the binary string.

Bonus One-Liner Method 5: Using Lambda and Reduce

A functional one-liner implementation can be created using Python’s reduce function and a lambda expression to cumulatively determine the DFA state. It’s concise but might be less readable for those unfamiliar with functional programming concepts.

Here’s an example:

from functools import reduce

is_multiple_of_three = lambda b: reduce(lambda s, c: (s << 1 | int(c)) % 3, b, 0) == 0

# Example usage:
print(is_multiple_of_three('110'))

Output:

True

This one-liner uses reduce to compactly fold the binary string into a single state that is compared with 0. The lambda function adjusts the state based on the current bit and the accumulated state.

Summary/Discussion

  • Method 1: Implementing DFA from Scratch. Strengths: Direct and educative approach. Weaknesses: May be less efficient due to on-the-fly transition calculation.
  • Method 2: Using Transition Table. Strengths: Precomputed transitions for improved speed. Weaknesses: Less flexible if the DFA design changes.
  • Method 3: Recursive State Transitions. Strengths: Elegant and compact code. Weaknesses: Limited by Python’s recursion depth and slower due to function calls.
  • Method 4: Object-Oriented DFA. Strengths: Clear structure, reusability, and maintainability. Weaknesses: Slight overhead of class instantiation.
  • Method 5: Using Lambda and Reduce. Strengths: Very concise code. Weaknesses: Potentially confusing for those not versed in functional programming.