เราได้รับลำดับไบนารีสามลำดับ A, B และ C ความยาว N แต่ละลำดับแทนจำนวนไบนารี เราต้องหาจำนวนการพลิกบิตที่ต้องการใน A และ B 使得 XOR ของ A และ B ได้ผลลัพธ์เป็น C นั่นคือ A XOR B กลายเป็น C
ก่อนอื่น ให้เรียนรู้ตารางความจริงของการดำเนินการ XOR —
| X | Y | 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}
เอาต์พุต
การพลิกที่ต้องการ: 2
วิธีการที่ใช้ในโปรแกรม
- อาร์เรย์ a[], b[] และ c[] ใช้เก็บหมายเลขไบนารี
- ฟังก์ชัน flipCount(int A[], int B[], int C[], int n) รับอาร์เรย์ a, b, c และความยาว n และคืนค่าจำนวนการพลิกที่ต้องการในบิตของ A[] หรือ B[] เพื่อได้ C[] เป็น A xor B
- ตัวแปร count แทนจำนวนการพลิก เริ่มต้นเป็น 0
- ใช้ลูป for วนแต่ละบิตในเซลล์จาก i = 0 ถึง i
- สำหรับแต่ละบิต A[i] และ B[i] ถ้าทั้งสองเท่ากันและ C[i] เป็น 1 ให้เพิ่ม count
- สำหรับแต่ละบิต A[i] และ B[i] ถ้าทั้งสองไม่เท่ากันและ C[i] เป็น 0 ให้เพิ่ม count
- คืนค่า count เป็นผลลัพธ์ที่ต้องการ
ตัวอย่างโค้ด
#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) {
// ถ้า A[i] และ B[i] เท่ากัน XOR ให้ 0 ถ้า C[i] เป็น 1 ให้พลิก
if (A[i] == B[i] && C[i] == 1)
++count;
// ถ้า A และ B ไม่เท่ากัน XOR ให้ 1 ถ้า C[i] เป็น 0 ให้พลิก
else if (A[i] != B[i] && C[i] == 0)
++count;
}
return count;
}
int main() {
// N แทนจำนวนบิตทั้งหมด
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 << "บิตขั้นต่ำที่ต้องพลิกให้ XOR ของ A และ B เท่ากับ C: " << flipCount(a, b, c, N);
return 0;
}
ผลลัพธ์
บิตขั้นต่ำที่ต้องพลิกให้ XOR ของ A และ B เท่ากับ C: 2
