พลิกขั้นต่ำในสองอาร์เรย์ไบนารีเพื่อให้ XOR ของพวกเขาเท่ากับอาร์เรย์อื่นใน C ++

คำชี้แจงปัญหา

กำหนดอาร์เรย์สามชุดที่มีขนาด n เท่ากับ 0 และ 1 ภารกิจคือค้นหาการพลิกกลับของบิตขั้นต่ำในอาร์เรย์ที่หนึ่งและที่สอง โดยที่ XOR ของบิตดัชนี i'th ของอาร์เรย์ที่หนึ่งและที่สองจะเท่ากับบิตดัชนีของ i'th อาร์เรย์ที่สาม

โปรดทราบว่าเราสามารถพลิกได้มากที่สุด p บิตของอาร์เรย์ 1 และมากที่สุด q บิตของอาร์เรย์ 2 นอกจากนี้ยังไม่อนุญาตให้จัดเรียงองค์ประกอบอาร์เรย์ใหม่

สมมุติว่า p =2 และ q =5

arr1[] ={1, 0, 1, 1, 0, 1, 0}arr2[] ={0, 1, 0, 1, 0, 0, 1}arr3[] ={0, 1, 1, 0, 0, 0, 0}

(arr1[0] ^ arr2[0]) คือ (1 ^ 0) =1 ซึ่งไม่เท่ากับ arr3[0] จึงต้องพลิกกลับ
(arr1[1] ^ arr2[1]) เช่น (0 ^ 1) =1 ซึ่งเท่ากับ arr3[1] ดังนั้นจึงไม่จำเป็นต้องพลิก
(arr1[2] ^ arr2[2]) เช่น (1 ^ 0) =1 ซึ่งเท่ากับ arr3[2] ดังนั้นจึงไม่จำเป็นต้องพลิก
(arr1[3] ^ arr2[3]) เช่น (1 ^ 1) =0 ซึ่งเท่ากับ arr3[3] ดังนั้นจึงไม่จำเป็นต้องพลิก
(arr1[4] ^ arr2[4]) เช่น (0 ^ 0) =0 ซึ่งเท่ากับ arr3[4] ดังนั้นจึงไม่จำเป็นต้องพลิก
(arr1[5] ^ arr2[5]) เช่น (1 ^ 0) =1 ซึ่งไม่เท่ากับ arr3[5] จึงต้องพลิกกลับ
(arr1[6] ^ arr2[6]) เช่น (0 ^ 1) =1 ซึ่งไม่เท่ากับ arr3[6] จึงต้องพลิกกลับ

อัลกอริทึม

<ก่อน>1. ถ้า (arr1[i] ^ arr2[i]) ==arr3[i] ให้ดำเนินการต่อเนื่องจากไม่จำเป็นต้องพลิก ถ้า (arr1[i] ^ arr2[i]) !=arr3[i] จำเป็นต้องพลิก ก. ถ้า arr3[i] ==0 แสดงว่าเงื่อนไขใดเงื่อนไขหนึ่งต่อไปนี้เป็นจริง:(arr1[i] ==0) และ (arr2[i] ==0) หรือ ii (arr1[i] ==1) และ (arr2[i] ==1) b. ถ้า arr3[i] ==1 เงื่อนไขใดเงื่อนไขหนึ่งต่อไปนี้เป็นจริง:(arr1[i] ==0) และ (arr2[0] ==1) หรือ ii (arr1[i] ==1) และ (arr2[i] ==0)3 หากต้องการพลิก เราสามารถพลิก arr1[i] หรือ arr2[i] ได้ ดังนั้นเราสามารถสรุปได้ว่าจำนวนการพลิกที่จำเป็นเพื่อให้ XOR ของ arr1 และ arr2 เท่ากับ arr3 ควรน้อยกว่าหรือเท่ากับ p + q

ตัวอย่าง

#include #define SIZE(arr) (sizeof(arr) / sizeof(arr[0])) โดยใช้เนมสเปซ std;int getRequiredFlips(int *arr1, int *arr2, int *arr3, int n, int p, int q) { int พลิก =0; สำหรับ (int i =0; i  ผลลัพธ์
 
 เมื่อคุณคอมไพล์และรันโปรแกรมข้างต้น มันสร้างผลลัพธ์ต่อไปนี้ -
 ต้องพลิก:3