Python Program to Count Minimum Bits to Flip such that XOR of A and B Equal to C

Given an N-bit binary sequence consisting of three binary sequences A, B, and C. Count the minimal number of bits required to flip A and B in such a way that the XOR of A and B equals C.

X       Y      X XOR Y

0       0        0

0       1        1

1       0        1

1       1        0

Cases:

  • If A[i]==B[i] and C[i]==0 then no flip,
  • If A[i]==B[i] and C[i]==1 then flip either A[i] or B[i] and increase flip count by 1
  • If A[i]!=B[i] and C[i]==0 then flip either A[i] or B[i] and increase flip count by 1
  • If A[i]!=B[i] and C[i]==1 then no flip required.

Examples:

Example1:

Input:

Given number = 5
Given first string=  "11011"
Given second string= "11001"
Given third string = "11100"

Output:

The count of minimum bits to Flip in such a way that the XOR of A and B equals C =  4

Example2:

Input:

Given number = 3
Given first string= "110"
Given second string= "111"
Given third string = "101"

Output:

The count of minimum bits to Flip in such a way that the XOR of A and B equals C =  1

Program to Count Minimum Bits to Flip such that XOR of A and B Equal to C in Python

Below are the ways to Count the minimal number of bits required to flip A and B in such a way that the XOR of A and B equals C:

Method #1: Using For Loop (Static Input)

Approach:

  • Give the number (which is the count of bits) as static input and store it in a variable.
  • Give the first binary sequence string as static input and store it in another variable.
  • Give the second binary sequence string as static input and store it in another variable.
  • Give the third binary sequence string as static input and store it in another variable.
  • Pass the given three sequence strings and the given number as the arguments to the Flips_Count function.
  • Create a function to say Flips_Count which takes the given three sequence strings and the given number as the arguments and returns the count of minimum bits to Flip in such a way that the XOR of A and B equals C.
  • Take a variable say totl_cnt and initialize its value to 0.
  • Loop till the given number using the for loop.
  • Check if the fst_seqnce[itr] == scnd_seqnce[itr] and third_seqnce[itr] == ‘1’ using the if conditional statement.
  • If the statement is true, then increment the value of above totl_cnt by 1.
  • Store it in the same variable.
  • Check if the fst_seqnce[itr] != scnd_seqnce[itr] and third_seqnce[itr] == ‘0’ using the elif conditional statement.
  • If the statement is true, then increment the value of above totl_cnt by 1.
  • Store it in the same variable.
  • Return the value of totl_cnt.
  • Print the count of minimum bits to Flip in such a way that the XOR of A and B equals C.
  • The Exit of the Program.

Below is the implementation:

# Create a function to say Flips_Count which takes the given three sequence
# strings and the given number as the arguments and returns the count of minimum bits
# to Flip in such a way that the XOR of A and B equals C.


def Flips_Count(fst_seqnce, scnd_seqnce, third_seqnce, numb):
    # Take a variable say totl_cnt and initialize its value to 0.
    totl_cnt = 0
    # Loop till the given number using the for loop.
    for itr in range(numb):
        # Check if the fst_seqnce[itr] == scnd_seqnce[itr] and third_seqnce[itr] == '1'
        # using the if conditional statement.
        if fst_seqnce[itr] == scnd_seqnce[itr] and third_seqnce[itr] == '1':
          # If the statement is true, then increment the value of above totl_cnt by 1.
          # Store it in the same variable.
            totl_cnt = totl_cnt+1

        # Check if the fst_seqnce[itr] != scnd_seqnce[itr] and third_seqnce[itr] == '0' using
        # the elif conditional statement.
        elif fst_seqnce[itr] != scnd_seqnce[itr] and third_seqnce[itr] == '0':
          # If the statement is true, then increment the value of above totl_cnt by 1.
          # Store it in the same variable.
            totl_cnt = totl_cnt+1
    # Return the value of totl_cnt.
    return totl_cnt


# Give the number (which is the count of bits) as static input and store it in a variable.
numb = 5
# Give the first binary sequence string as static input and store it in another variable.
fst_seqnce = "11011"
# Give the second binary sequence string as static input and store it in another variable.
scnd_seqnce = "11001"
# Give the third binary sequence string as static input and store it in another variable.
third_seqnce = "11100"
# Pass the given three sequence strings and the given number as the arguments to the
# Flips_Count function.
# Print the count of minimum bits to Flip in such a way that the XOR of A and B equals C.
print("The count of minimum bits to Flip in such a way that the XOR of A and B equals C = ",
      Flips_Count(fst_seqnce, scnd_seqnce, third_seqnce, numb))

Output:

The count of minimum bits to Flip in such a way that the XOR of A and B equals C =  4

Method #2: Using For loop (User Input)

Approach:

  • Give the number (which is the count of bits) as user input using the int(input()) function and store it in a variable.
  • Give the first binary sequence string as user input using the input() function and store it in another variable.
  • Give the second binary sequence string as user input using the input() function and store it in another variable.
  • Give the third binary sequence string as user input using the input() function and store it in another variable.
  • Pass the given three sequence strings and the given number as the arguments to the Flips_Count function.
  • Create a function to say Flips_Count which takes the given three sequence strings and the given number as the arguments and returns the count of minimum bits to Flip in such a way that the XOR of A and B equals C.
  • Take a variable say totl_cnt and initialize its value to 0.
  • Loop till the given number using the for loop.
  • Check if the fst_seqnce[itr] == scnd_seqnce[itr] and third_seqnce[itr] == ‘1’ using the if conditional statement.
  • If the statement is true, then increment the value of above totl_cnt by 1.
  • Store it in the same variable.
  • Check if the fst_seqnce[itr] != scnd_seqnce[itr] and third_seqnce[itr] == ‘0’ using the elif conditional statement.
  • If the statement is true, then increment the value of above totl_cnt by 1.
  • Store it in the same variable.
  • Return the value of totl_cnt.
  • Print the count of minimum bits to Flip in such a way that the XOR of A and B equals C.
  • The Exit of the Program.

Below is the implementation:

# Create a function to say Flips_Count which takes the given three sequence
# strings and the given number as the arguments and returns the count of minimum bits
# to Flip in such a way that the XOR of A and B equals C.


def Flips_Count(fst_seqnce, scnd_seqnce, third_seqnce, numb):
    # Take a variable say totl_cnt and initialize its value to 0.
    totl_cnt = 0
    # Loop till the given number using the for loop.
    for itr in range(numb):
        # Check if the fst_seqnce[itr] == scnd_seqnce[itr] and third_seqnce[itr] == '1'
        # using the if conditional statement.
        if fst_seqnce[itr] == scnd_seqnce[itr] and third_seqnce[itr] == '1':
          # If the statement is true, then increment the value of above totl_cnt by 1.
          # Store it in the same variable.
            totl_cnt = totl_cnt+1

        # Check if the fst_seqnce[itr] != scnd_seqnce[itr] and third_seqnce[itr] == '0' using
        # the elif conditional statement.
        elif fst_seqnce[itr] != scnd_seqnce[itr] and third_seqnce[itr] == '0':
          # If the statement is true, then increment the value of above totl_cnt by 1.
          # Store it in the same variable.
            totl_cnt = totl_cnt+1
    # Return the value of totl_cnt.
    return totl_cnt


# Give the number (which is the count of bits) as user input using the int(input()) function 
# and store it in a variable.
numb = int(input('Enter some random number = '))
# Give the first binary sequence string as user input using the input() function and 
# store it in another variable.
fst_seqnce = input('Enter some random binary number string  = ')
# Give the second binary sequence string as user input using the input() function and 
# store it in another variable.
scnd_seqnce = input('Enter some random binary number string  = ')
# Give the third binary sequence string as user input using the input() function and 
# store it in another variable.
third_seqnce = input('Enter some random binary number string  = ')
# Pass the given three sequence strings and the given number as the arguments to the
# Flips_Count function.
# Print the count of minimum bits to Flip in such a way that the XOR of A and B equals C.
print("The count of minimum bits to Flip in such a way that the XOR of A and B equals C = ",
      Flips_Count(fst_seqnce, scnd_seqnce, third_seqnce, numb))

Output:

Enter some random number = 3
Enter some random binary number string = 110
Enter some random binary number string = 111
Enter some random binary number string = 101
The count of minimum bits to Flip in such a way that the XOR of A and B equals C = 1

Leave a Comment