Bit Manipulationmedium
1 views

Toggle Bit to Check Multiple of 5 in Binary Representation

Check if a binary number can become a multiple of 5 by toggling exactly one bit

Understand the Problem

Problem Statement

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 in its binary representation.

A toggle operation changes a single bit from 0 to 1 or from 1 to 0.

Constraints

  • 1 ≤ N < 231
  • Input is a valid binary string with no leading zeros
  • Binary string length will be at most 31 characters
  • Exactly one bit must be toggled (cannot toggle zero or multiple bits)

Examples

Example 1
Input
1101
Output
Yes
Explanation

Binary 1101 equals 13 in decimal. Toggling the first bit gives 0101 (5), which is divisible by 5. Toggling the third bit gives 1111 (15), which is also divisible by 5.

Example 2
Input
1010
Output
No
Explanation

Binary 1010 equals 10 in decimal. Toggling any single bit produces 0010 (2), 1110 (14), 1000 (8), or 1011 (11), none of which are divisible by 5.

Solution

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int toggle_bit(int n, int k) {
    return n ^ (1 << (k - 1));
}

int main() {
    char binary[32];
    scanf("%s", binary);
    
    int decimal = 0;
    int len = strlen(binary);
    
    // Convert binary string to decimal
    for (int i = 0; i < len; i++) {
        decimal = decimal * 2 + (binary[i] - '0');
    }
    
    // Check each bit position
    for (int i = 1; i <= len; i++) {
        if (toggle_bit(decimal, i) % 5 == 0) {
            printf("Yes\n");
            return 0;
        }
    }
    
    printf("No\n");
    return 0;
}
Time:O(log N) where N is the decimal value, since we iterate through each bit position
Space:O(1) - only using a constant amount of extra space for variables
Approach:

The C solution follows the same approach:

  1. Read the binary string using scanf
  2. Convert to decimal by iterating through each character and multiplying by powers of 2
  3. Use the toggle_bit function that applies XOR with a left-shifted 1 to toggle the specified bit
  4. Check divisibility by 5 for each toggle result
  5. Exit early if a valid toggle is found, otherwise print "No"

The solution efficiently handles the bit manipulation using C's bitwise operators.

Visual Explanation

Loading diagram...
All ProblemsMore Bit Manipulation