Java Program to Check if Binary Number is Multiple of 3

Binary numbers play a vital role computer science. It shows information using only the numbers 0 and 1. Determining whether a binary number is divisible by 3 or not is an understanding of modular arithmetic, numbers and multipliers is required.

A binary number can be analyzed to determine divisibility by converting it to its decimal equivalent or directly evaluating its properties using rules based on modulus arithmetic.

Core Concept Behind the Solution

The algorithm for checking whether a binary number is divisible by 3 depends on the properties of the parameter operation. The binary numbers d_n , d_n-1 can be considered as strings of numbers …. d₁, d₀ where d_i {0, 1}. The decimal equivalent is calculated as:

Using modulus properties, we can avoid converting the entire binary number into decimal form. Instead, we evaluate the number iteratively while keeping track of its remainders when divided by 3.

Observations

1. A binary number is divisible by 3 if the weighted sum of its digits, computed modulo 3, results in 0.
2. The state of the remainder depends on the incoming binary digit (0 or 1), and we can define a state transition table for the remainders:
   
   • Remainder 0 transitions to 0 or 1.
   • Remainder 1 transitions to 2 or 0.
   • Remainder 2 transitions to 1 or 2.

Example

Input: 110

1. Start with state 0.
2. Read 1: Transition from 0 to 1.
3. Read 1: Transition from 1 to 2.
4. Read 0: Stay at 2.
5. Final state: 2 (not divisible by 3).

Output: The binary number is not a multiple of 3.

Let's implement the above approach in a Java program.

File Name: BinaryMultipleOfThree.java

Output:

 Enter a binary number: 110 The binary number is not a multiple of 3. 

Explanation

The Java program checks if a binary number is divisible by 3 using a finite state machine (FSM) approach. It processes the binary string bit by bit, tracking the remainder when divided by 3 using a state variable (0, 1, 2). Starting from the initial state 0, the program transitions between states based on the current bit (0 or 1).

For example, a 1 advances the state (for example, 0 to 1), while a 0 keeps it unchanged. Invalid input (non-binary characters) is handled by throwing an exception. After processing all bits, if the state remains 0, the binary number is divisible by 3. It avoids converting the binary string to decimal, ensuring efficiency and scalability.

Key Features of the Program

1. Efficient Modulus Calculation
   
   • Instead of converting the binary number into its decimal form (which could result in overflow for large inputs), the program processes the number bit by bit.
   • This ensures that the algorithm runs in (O(n)), where (n) is the length of the binary string.
2. FSM-Based Design
   
   • The finite state machine ensures that the program maintains a compact representation of the remainder at all times.
3. Robust Error Handling
   
   • The program detects invalid inputs (e.g., containing characters other than 0 and 1) and handles them appropriately.

Advantages of the Approach

1. Scalability: The algorithm handles binary numbers of arbitrary lengths without converting them to decimal.
2. Low Memory Usage: The program uses only a single integer (state) to track the remainder.
3. Simplicity: The FSM-based approach is intuitive and avoids complex calculations.

Complexity Analysis

Time Complexity: The algorithm runs in (O(n)), where (n) is the length of the binary string. Each bit is processed exactly once, making the operation linear.

Space Complexity: The program uses (O(1)) space since it maintains only a single state variable and does not require additional storage proportional to the input size.

Conclusion

The program efficiently determines if a binary number is a multiple of 3 using a simple yet powerful FSM-based approach. By leveraging modular arithmetic, it eliminates the need for large-number computations, making it robust and suitable for handling long binary strings.

Its linear time complexity ensures fast execution, while its low space requirement guarantees minimal resource usage. This method exemplifies how mathematical insights can lead to elegant and practical algorithm designs.