- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

We are given with three binary sequences A, B and C of length N. Each sequence represents a binary number. We have to find no. of flips required of bits in A and B such that XOR of A and B results in C. A XOR B becomes C.

First of all let us learn about truth table of XOR operation −

X | Y | X XOR Y |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

From the above table we observe that for the same values in X and Y, X XOR Y results 0 else it results 1. So this will be helpful for finding bits to be flipped in A and B to reach C. Cases will be

- 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.

A[]= { 0,0,0,0 } B[]= { 1,0,1,0 } C= {1,1,1,1}

Required flips : 2

A[0] xor B[0] 0 xor 1 = 1 C[0]=1 no flip A[1] xor B[1] 0 xor 0 = 0 C[0]=1 flip count=1 A[2] xor B[2] 0 xor 1 = 1 C[0]=1 no flip A[3] xor B[3] 0 xor 0 = 0 C[0]=1flip count=2

A[]= { 0,0,1,1 } B[]= { 0,0,1,1 } C= {0,0,1,1}

Required flips : 2

A[0] xor B[0] 0 xor 0 = 0 C[0]=0 no flip A[1] xor B[1] 0 xor 0 = 0 C[0]=0 no flip A[2] xor B[2] 1 xor 1 = 0 C[0]=1 flip count=1 A[3] xor B[3] 1 xor 1 = 0 C[0]=1 flip count=2

Arrays a[], b[] and c[] are used to store binary no’s.

Function flipCount(int A[], int B[], int C[], int n) takes arrays a, b, c and their length n as input and returns the count of flips required in bits of either A[] or B[] to get C[] as A xor B

Variable count represents flip count and initialized with 0.

Using for loop traverse each bit in the cell from i = 0 to i

For each bit A[i] and B[i]. if they are equal and C[i] is 1 increase count.

For each bit A[i] and B[i]. if they are not equal and C[i] is 0 increase count.

Return the count as desired result.

#include<bits/stdc++.h> using namespace std; int flipCount(int A[], int B[], int C[], int N){ int count = 0; for (int i=0; i < N; ++i){ // If both A[i] and B[i] are equal then XOR results 0, if C[i] is 1 flip if (A[i] == B[i] && C[i] == 1) ++count; // If Both A and B are unequal then XOR results 1 , if C[i] is 0 flip else if (A[i] != B[i] && C[i] == 0) ++count; } return count; } int main(){ //N represent total count of Bits int N = 5; int a[] ={1,0,0,0,0}; int b[] ={0,0,0,1,0}; int c[] ={1,0,1,1,1}; cout <<"Minimum bits to flip such that XOR of A and B equal to C :"<<flipCount(a, b, c,N); return 0; }

Minimum bits to flip such that XOR of A and B equal to C :2

- Related Questions & Answers
- Count pairs in an array such that both elements has equal set bits in C++
- Minimum Flips to Make a OR b Equal to c in C++
- Count number of triplets (a, b, c) such that a^2 + b^2 = c^2 and 1<=a<=b<=c<= n in C++
- Count of all possible values of X such that A % X = B in C++
- Count Triplets That Can Form Two Arrays of Equal XOR in C++
- Count number of pairs (A <= N, B <= N) such that gcd (A , B) is B in C++
- XOR of all elements of array with set bits equal to K in C++
- Count the triplets such that A[i] < B[j] < C[k] in C++
- Find four elements a, b, c and d in an array such that a+b = c+d in C++
- Equal Sum and XOR in C++
- Find minimum positive integer x such that a(x^2) + b(x) + c >= k in C++
- Find the minimum positive integer such that it is divisible by A and sum of its digits is equal to B in Python
- Count pairs (i,j) such that (i+j) is divisible by both A and B in C++
- Count ordered pairs of positive numbers such that their sum is S and XOR is K in C++
- Count the number of rectangles such that ratio of sides lies in the range [a,b] in C++.

Advertisements