Toggle Bit to Check Multiple of 5 in Binary Representation

This article explains a Python program that checks whether a binary number can be converted to a multiple of 5 by toggling exactly one bit in its binary representation. This problem involves binary arithmetic and bit manipulation, making it an interesting use case for learning these techniques.

---

Problem Description

Task:
Given the binary representation of an integer N, determine if it is possible to convert N into a multiple of 5 by toggling exactly one bit.

Boundary Condition:

• 1 ≤ N < 231 .

Input Format:

• The first line contains the binary representation of the integer N.

Output Format:

• Print “Yes” if N can become a multiple of 5 by toggling one bit; otherwise, print “No”.

---

Example Input/Output

Example 1:

Input:

1101

Output:

Yes

Explanation:
The binary number 1101 is equivalent to 1313 in decimal.
By toggling exactly one bit, we can generate the following binary numbers:

• 0101 (decimal 5, a multiple of 5)
• 1001 (decimal 9, not a multiple of 5)
• 1111 (decimal 15, a multiple of 5)
• 1100 (decimal 12, not a multiple of 5)

Since 55 and 1515 are multiples of 5, the output is “Yes”.

---

Example 2:

Input:

1010

Output:

No

Explanation:
The binary number 1010 is equivalent to 1010 in decimal.
By toggling exactly one bit, we can generate the following binary numbers:

• 0010 (decimal 2, not a multiple of 5)
• 1110 (decimal 14, not a multiple of 5)
• 1000 (decimal 8, not a multiple of 5)
• 1011 (decimal 11, not a multiple of 5)

Since no multiple of 5 can be formed, the output is “No”.

---

Python Code

def toggle_bit(n, k):
    # Toggle the k-th bit using XOR operation
    return n ^ (1 << (k - 1))

# Read the binary input as a string
binary_input = input().strip()

# Convert binary string to an integer
decimal_value = int(binary_input, 2)

# Iterate over each bit position
for i in range(1, len(binary_input) + 1):
    # Toggle the i-th bit and check if it becomes a multiple of 5
    if toggle_bit(decimal_value, i) % 5 == 0:
        print("Yes")
        exit()

# If no multiple of 5 is found, print No
print("No")

---

Explanation of the Code

1. Function to Toggle a Bit:
   • The toggle_bit function uses XOR (^) to toggle the bit at a specific position k.
   • 1 << (k - 1) generates a number with only the k-th bit set to 1.
   • XOR flips the k-th bit of the number.
2. Binary to Decimal Conversion:
   • The⁣ int(s, 2) function converts the binary string s to its decimal equivalent.
3. Iterate Over Bit Positions:
   • The program loops through all bit positions from 1 to the length of the binary string.
   • For each bit position, it toggles the bit and checks if the resulting number is divisible by 5.
4. Output Result:
   • If any toggled value is a multiple of 5, the program prints “Yes” and exits.
   • If the loop completes without finding any such value, the program prints “No”.

---

Key Concepts and Keywords

• Binary to Decimal Conversion: Convert binary numbers to decimal for arithmetic operations.
• Bit manipulation: Use XOR and bit-shifting to toggle bits.
• Modulo Operator: Check divisibility by 5.
• Efficient Search: Minimize computations by checking each toggle possibility.

---

Edge Cases

1. Single Toggle Possible:
   • Input: 1001
   • Output: Yes
     Explanation: Toggle the last bit to make 1011, which equals 15.
2. Already Multiple of 5:
   • Input: 101
   • Output: Yes
     Explanation: Even if a toggle is not necessary, toggling a bit can still produce another multiple of 5.
3. Maximum Binary Length:
   • Input: 30-bit binary string
   • Ensure the program handles the largest input within boundary conditions.

---

Conclusion

This program effectively solves the problem using bit manipulation and binary arithmetic. It is efficient for the given constraints and demonstrates a practical approach to working with binary data in Python.