Chúng ta được cung cấp với ba dãy nhị phân A, B và C có độ dài N. Mỗi dãy biểu diễn số nhị phân. Chúng tôi phải tìm thấy không. trong số các lần lật bắt buộc của các bit trong A và B sao cho XOR của A và B dẫn đến C. A XOR B trở thành C.
Trước hết, chúng ta hãy tìm hiểu về bảng sự thật của phép toán XOR -
| X | Y | X XOR Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Từ bảng trên, chúng ta quan sát thấy rằng đối với các giá trị giống nhau trong X và Y, X XOR Y cho kết quả bằng 0 khác kết quả là 1. Vì vậy, điều này sẽ hữu ích cho việc tìm kiếm các bit được lật trong A và B để đạt được C. Các trường hợp sẽ là
- Nếu A [i] ==B [i] và C [i] ==0 thì không lật,
- Nếu A [i] ==B [i] và C [i] ==1 thì lật A [i] hoặc B [i] và tăng số lần lật lên 1
- Nếu A [i]! =B [i] và C [i] ==0 thì lật A [i] hoặc B [i] và tăng số lần lật lên 1
- Nếu A [i]! =B [i] và C [i] ==1 thì không cần lật.
Đầu vào
A[]= { 0,0,0,0 } B[]= { 1,0,1,0 } C= {1,1,1,1} Đầu ra
Required flips : 2
Giải thích
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
Đầu vào
A[]= { 0,0,1,1 } B[]= { 0,0,1,1 } C= {0,0,1,1} Đầu ra
Required flips : 2
Giải thích
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
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
-
Mảng a [], b [] và c [] được sử dụng để lưu trữ số nhị phân.
-
Hàm flipCount (int A [], int B [], int C [], int n) nhận mảng a, b, c và độ dài n asinput của chúng và trả về số lần lật bắt buộc tính bằng bit của A [] hoặc B [ ] để lấy C [] là A xorB
-
Số lượng biến thể hiện số lần lật và được khởi tạo bằng 0.
-
Sử dụng vòng lặp for duyệt từng bit trong ô từ i =0 đến i
-
Đối với mỗi bit A [i] và B [i]. nếu chúng bằng nhau và C [i] là 1 số tăng.
-
Đối với mỗi bit A [i] và B [i]. nếu chúng không bằng nhau và C [i] là 0 số tăng.
-
Trả lại số lượng như kết quả mong muốn.
Ví dụ
#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;
} Đầu ra
Minimum bits to flip such that XOR of A and B equal to C :2