เราได้รับด้วยลำดับไบนารีสามชุด A, B และ C ที่มีความยาว N แต่ละลำดับแสดงถึงเลขฐานสอง เราต้องหาไม่ ของการพลิกที่ต้องการของบิตใน A และ B โดยที่ XOR ของ A และ B ส่งผลให้ C. A XOR B กลายเป็น C.
ก่อนอื่นให้เราเรียนรู้เกี่ยวกับตารางความจริงของการดำเนินการ XOR -
| X | ย | X XOR Y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
จากตารางด้านบนเราสังเกตว่าสำหรับค่าเดียวกันใน X และ Y X XOR Y จะให้ผลลัพธ์เป็น 0 อย่างอื่นเป็นผลลัพธ์ 1 ดังนั้นสิ่งนี้จะเป็นประโยชน์สำหรับการค้นหาบิตที่จะพลิกใน A และ B เพื่อไปถึง C กรณีต่างๆ จะเป็น
- ถ้า A[i]==B[i] และ C[i]==0 แล้วไม่มีการพลิกกลับ
- หาก A[i]==B[i] และ C[i]==1 ให้พลิก A[i] หรือ B[i] และเพิ่มจำนวนการพลิกขึ้น 1
- หาก A[i]!=B[i] และ C[i]==0 ให้พลิก A[i] หรือ B[i] และเพิ่มจำนวนการพลิกขึ้น 1
- ถ้า A[i]!=B[i] และ C[i]==1 ไม่จำเป็นต้องพลิกกลับ
อินพุต
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
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
อาร์เรย์ a[], b[] และ c[] ใช้เพื่อจัดเก็บเลขฐานสองของ
-
ฟังก์ชั่น flipCount(int A[], int B[], int C[], int n) รับอาร์เรย์ a, b, c และความยาว n asinput และส่งกลับจำนวนการพลิกที่ต้องการในบิตของ A[] หรือ B[ ] เพื่อรับ C[] เป็น A xorB
-
จำนวนตัวแปรแสดงถึงจำนวนการพลิกและเริ่มต้นด้วย 0
-
ใช้สำหรับวนรอบแต่ละบิตในเซลล์จาก i =0 ถึง i
-
สำหรับแต่ละบิต A[i] และ B[i] หากเท่ากันและ C[i] จะเพิ่มขึ้น 1 ครั้ง
-
สำหรับแต่ละบิต A[i] และ B[i] หากไม่เท่ากันและ C[i] จะเพิ่มขึ้นเป็น 0
-
คืนจำนวนตามผลลัพธ์ที่ต้องการ
ตัวอย่าง
#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
