Java Program to Check if a Binary String is a Multiple of 3 Using DFA

A binary string is a sequence of digits containing only 0s and 1s. Determining whether a given binary string represents a number that is a multiple of 3 is a classic problem in the theory of computation and finite automata.

One of the most efficient ways to solve this problem is by using a Deterministic Finite Automaton (DFA). The DFA processes the binary string character by character and maintains a state that determines whether the corresponding decimal value is divisible by 3.

Problem Statement

Given a binary string and the task is to check whether the decimal representation of the binary number is a multiple of 3. DFA can be constructed with a limited number of states to efficiently determine the divisibility condition without converting the entire binary number to decimal explicitly.

Examples:

Example 1:

Input: "110"

Output: Yes

Explanation

For the binary string "110", the decimal equivalent is calculated as 1 × 2^2 + 1 × 2^1 + 0 × 2^0 = 4 + 2 + 0 = 6. Since 6 is divisible by 3, the DFA reaches state 0, which represents numbers that are multiples of 3. Therefore, the output is Yes.

Example 2:

Input: "101"

Output: No

Explanation

For the binary string "101", the decimal value is determined as 1 × 2^2 + 0 × 2^1 + 1 × 2^0 = 4 + 0 + 1 = 5. Since 5 is not divisible by 3, the DFA does not end in state 0, indicating that the number is not a multiple of 3. Hence, the output is No.

Example 3:

Input: "1111"

Output: Yes

Explanation

For the binary string "1111", the decimal equivalent is calculated as 1 × 2^3 + 1 × 2^2 + 1 × 2^1 + 1 × 2^0 = 8 + 4 + 2 + 1 = 15. Since 15 is divisible by 3 the DFA reaches state 0 by confirming that the number is a multiple of 3. Therefore, the output is Yes.

Approach 1: Using DFA (Deterministic Finite Automaton)

Algorithm

Step 1: Initialize the state as 0, which represents numbers that are divisible by 3.

Step 2: Iterate through each bit of the binary string by converting it into a character array for easy processing.

Step 3: Based on the current bit and transition between states as follows:

Step 3.1: If the bit is 0:

Step 3.1.1: Stay in state 0 if already in state 0.

Step 3.1.2: Move to state 2 if in state 1.

Step 3.1.3: Move to state 1 if in state 2.

Step 3.2: If the bit is 1:

Step 3.2.1: Move to state 1 if in state 0.

Step 3.2.2: Move to state 0 if in state 1.

Step 3.2.3: Stay in state 2 if already in state 2.

Step 4: If the binary string contains any character other than 0 or 1 then return false immediately.

Step 5: After processing all bits then check the final state. If the state is 0, then return true, which indicates that the number is divisible by 3. Otherwise, return false.

Step 6: The function returns the result based on the final state and completing the process.

Implementation

Output:

 Input: 110 -> Output: Yes Input: 101 -> Output: No Input: 1111 -> Output: Yes 

Complexity Analysis

Time Complexity

The time complexity of this algorithm is O(N), where N is the length of the binary string, since each bit is processed exactly once.

Space Complexity

The space complexity is O(1) as only a few integer variables are used, which requires constant space.

Approach 2: Using Recursion to Compute Remainder

Algorithm

Step 1: Start by defining a recursive function that computes the remainder when the binary number is divided by 3. The function takes the binary string, the current index, and the remainder as parameters. If the index reaches the length of the string, then return the final remainder.

Step 2: Extract the current bit from the binary string by converting the character to an integer (0 or 1). Update the remainder using the following formula:

This step ensures that the remainder is continuously updated based on the bits processed so far.

Step 3: Make a recursive call to process the next bit in the binary string, incrementing the index by 1. It continues until all bits have been processed.

Step 4: In the main function, validate the input by checking if the binary string contains only 0 and 1. If the input contains invalid characters, then return false.

Step 5: Call the recursive function with an initial remainder of 0 and an index of 0. After processing all bits and check if the final remainder is 0. If it is, then return true, indicating that the number is a multiple of 3; otherwise, return false.

Step 6: Print the result for multiple test cases, then demonstrate that the function correctly determines whether a given binary string represents a number that is divisible by 3.

Implementation

Output:

 Input: 110 -> Output: Yes Input: 101 -> Output: No Input: 1111 -> Output: Yes 

Complexity Analysis

Time Complexity

The time complexity of this algorithm is O(N), where N is the length of the binary string since each bit is processed once.

Space Complexity

The space complexity is O(N) due to the recursive call stack, which grows linearly with the length of the input string.

Approach 3: Using the Divide and Conquer Technique

Algorithm

Step 1: If the binary string is empty, then return 0 as the remainder. If it contains only one bit, then compute its remainder when divided by 3 and return that value. It serves as the base case for the recursion.

Step 2: Divide the binary string into two halves. The first half consists of the leftmost bits, and the second half consists of the rightmost bits.

Step 3: Recursively compute the remainder of the left half and the right half separately using the same function. Each recursive call continues dividing the string until the base case is reached.

Step 4: Compute the power of two for the length of the right half modulo 3. It ensures that when merging the results of both halves, the contribution of the left half is correctly scaled in modular arithmetic.

Step 5: Combine the remainder of the left half and right half using the formula (left remainder * power + right remainder) % 3. The step merges the results while maintaining correctness in modular arithmetic.

Step 6: If the final remainder is 0, then the binary string represents a number divisible by 3, so return true. Otherwise, return false.

Implementation

Output:

 Input: 110 -> Output: Yes Input: 101 -> Output: No Input: 1111 -> Output: Yes 

Complexity Analysis

Time Complexity

The time complexity of this approach is O(N log N) because the function recursively splits the binary string, leading to a logarithmic depth, and each level processes part of the string.

Space Complexity

The space complexity is O(log N) due to the recursive function calls stored in the call stack.