logo

ספור ביטים מינימליים להיפוך כך ש-XOR של A ו-B שווה ל-C

נתון רצף של שלושה רצפים בינאריים A B ו-C של N ביטים. ספור את הסיביות המינימליות הנדרשות כדי להפוך את A ו-B כך ש-XOR של A ו-B שווה ל-C. דוגמה:  
 

Input: N = 3 A = 110 B = 101 C = 001 Output: 1 We only need to flip the bit of 2nd position of either A or B such that A ^ B = C i.e. 100 ^ 101 = 001


 


א גישה נאיבית הוא ליצור את כל השילובים האפשריים של סיביות ב-A ו-B ולאחר מכן לבצע XOR כדי לבדוק אם זה שווה ל-C או לא. מורכבות הזמן של גישה זו גדל באופן אקספוננציאלי ולכן לא יהיה טוב יותר עבור ערך גדול של N.
אַחֵר הגישה היא להשתמש במושג XOR. 
 



XOR Truth Table   Input     Output   X Y Z 0 0 - 0 0 1 - 1 1 0 - 1 1 1 - 0


אם נכליל נגלה שבכל מיקום של A ו-B אנחנו רק צריכים להפוך את iה'מיקום (0 עד N-1) של A או B אחרת לא נוכל להשיג מספר סיביות מינימלי. 
אז בכל מיקום של i (0 עד N-1) אתה תיתקל בשני סוגים של מצבים, כלומר או A[i] == B[i] או A[i] != B[i]. בואו נדון בזה אחד אחד. 
 


  • אם A[i] == B[i] אז XOR של סיביות אלו יהיה 0 שני מקרים עולים ב-C[]: C[i]==0 או C[i]==1. 
    אם C[i] == 0 אז אין צורך להפוך את הביט אבל אם C[i] == 1 אז עלינו להפוך את הביט ב-A[i] או ב-B[i] כך ש-1^0 == 1 או 0^1 == 1. 
     

  • אם A[i] != B[i] אז XOR של סיביות אלה נותן 1 ב-C שני מקרים עולים שוב כלומר או C[i] == 0 או C[i] == 1. 
    לכן אם C[i] == 1 אז אנחנו לא צריכים להפוך את הביט אבל אם C[i] == 0 אז אנחנו צריכים להפוך את הביט או ב-A[i] או ב-B[i] כך ש-0^0==0 או 1^1==0 
     


 

C++
// C++ code to count the Minimum bits in A and B #include   using namespace std; int totalFlips(char *A char *B char *C int N) {  int count = 0;  for (int i=0; i < N; ++i)  {  // If both A[i] and B[i] are equal  if (A[i] == B[i] && C[i] == '1')  ++count;  // If Both A and B are unequal  else if (A[i] != B[i] && C[i] == '0')  ++count;  }  return count; } //Driver Code int main() {  //N represent total count of Bits  int N = 5;  char a[] = '10100';  char b[] = '00010';  char c[] = '10011';  cout << totalFlips(a b c N);  return 0; } 
Java
// Java code to count the Minimum bits in A and B class GFG {    static int totalFlips(String A String B  String C int N)  {  int count = 0;    for (int i = 0; i < N; ++i)  {  // If both A[i] and B[i] are equal  if (A.charAt(i) == B.charAt(i) &&   C.charAt(i) == '1')  ++count;    // If Both A and B are unequal  else if (A.charAt(i) != B.charAt(i)  && C.charAt(i) == '0')  ++count;  }    return count;  }    //driver code  public static void main (String[] args)  {  //N represent total count of Bits  int N = 5;  String a = '10100';  String b = '00010';  String c = '10011';    System.out.print(totalFlips(a b c N));  } } // This code is contributed by Anant Agarwal. 
Python3
# Python code to find minimum bits to be flip def totalFlips(A B C N): count = 0 for i in range(N): # If both A[i] and B[i] are equal if A[i] == B[i] and C[i] == '1': count=count+1 # if A[i] and B[i] are unequal else if A[i] != B[i] and C[i] == '0': count=count+1 return count # Driver Code # N represent total count of Bits N = 5 a = '10100' b = '00010' c = '10011' print(totalFlips(a b c N)) 
C#
// C# code to count the Minimum // bits flip in A and B using System; class GFG {  static int totalFlips(string A string B  string C int N)  {  int count = 0;  for (int i = 0; i < N; ++i) {  // If both A[i] and B[i] are equal  if (A[i] == B[i] && C[i] == '1')  ++count;  // If Both A and B are unequal  else if (A[i] != B[i] && C[i] == '0')  ++count;  }  return count;  }  // Driver code  public static void Main()  {  // N represent total count of Bits  int N = 5;  string a = '10100';  string b = '00010';  string c = '10011';  Console.Write(totalFlips(a b c N));  } } // This code is contributed by Anant Agarwal. 
PHP
 // PHP code to count the // Minimum bits in A and B function totalFlips($A $B $C $N) { $count = 0; for ($i = 0; $i < $N; ++$i) { // If both A[i] and  // B[i] are equal if ($A[$i] == $B[$i] && $C[$i] == '1') ++$count; // If Both A and  // B are unequal else if ($A[$i] != $B[$i] && $C[$i] == '0') ++$count; } return $count; } // Driver Code // N represent total count of Bits $N = 5; $a = '10100'; $b = '00010'; $c = '10011'; echo totalFlips($a $b $c $N); // This code is contributed by nitin mittal. ?> 
JavaScript
<script> // Javascript code to count the Minimum bits in A and B   function totalFlips(A B C N)   {   let count = 0;   for (let i = 0; i < N; ++i) {     // If both A[i] and B[i] are equal   if (A[i] == B[i] && C[i] == '1')   ++count;     // If Both A and B are unequal   else if (A[i] != B[i] && C[i] == '0')   ++count;   }   return count;   }    // Driver Code    // N represent total count of Bits   let N = 5;   let a = '10100';   let b = '00010';   let c = '10011';     document.write(totalFlips(a b c N));    </script> 

תְפוּקָה
2


מורכבות זמן: עַל) 
חלל עזר: O(1)

גישה יעילה:

גישה זו עוקבת אחר מורכבות הזמן O(log N).

C++
// C++ code to count the Minimum bits in A and B #include    using namespace std; int totalFlips(string A string B string C int N) {  int INTSIZE = 31;  int ans = 0;  int i = 0;  while (N > 0) {  // Considering only 31 bits  int a = stoi(A.substr(i * INTSIZE min(INTSIZE N))  0 2);  int b = stoi(B.substr(i * INTSIZE min(INTSIZE N))  0 2);  int c = stoi(C.substr(i * INTSIZE min(INTSIZE N))  0 2);  int Z = a ^ b ^ c;  // builtin function for  // counting the number of set bits.  ans += __builtin_popcount(Z);  i++;  N -= 32;  }  return ans; } // Driver Code int main() {  // N represent total count of Bits  int N = 5;  char a[] = '10100';  char b[] = '00010';  char c[] = '10011';  cout << totalFlips(a b c N);  return 0; } // This code is contributed by Kasina Dheeraj. 
Java
// Java code to count the Minimum bits in A and B class GFG {  static int totalFlips(String A String B String C  int N)  {  int INTSIZE = 31;  int ans = 0;  int i = 0;  while (N > 0) {  // Considering only 31 bits  int a = Integer.parseInt(  A.substring(i * INTSIZE  i * INTSIZE  + Math.min(INTSIZE N))  2);  int b = Integer.parseInt(  B.substring(i * INTSIZE  i * INTSIZE  + Math.min(INTSIZE N))  2);  int c = Integer.parseInt(  C.substring(i * INTSIZE  i * INTSIZE  + Math.min(INTSIZE N))  2);  int Z = a ^ b ^ c;  // builtin function for  // counting the number of set bits.  ans += Integer.bitCount(Z);  i++;  N -= 32;  }  return ans;  }  // driver code  public static void main(String[] args)  {  // N represent total count of Bits  int N = 5;  String a = '10100';  String b = '00010';  String c = '10011';  System.out.print(totalFlips(a b c N));  } } // This code is contributed by Kasina Dheeraj. 
Python3
def totalFlips(A B C N): INTSIZE = 31 ans = 0 i = 0 while N > 0: # Considering only 31 bits a = int(A[i * INTSIZE: min(INTSIZE + i * INTSIZE N)] 2) b = int(B[i * INTSIZE: min(INTSIZE + i * INTSIZE N)] 2) c = int(C[i * INTSIZE: min(INTSIZE + i * INTSIZE N)] 2) Z = a ^ b ^ c # builtin function for counting the number of set bits. ans += bin(Z).count('1') i += 1 N -= 32 return ans # Driver Code if __name__ == '__main__': # N represent total count of Bits N = 5 a = '10100' b = '00010' c = '10011' print(totalFlips(a b c N)) 
C#
using System; class Program {  static int TotalFlips(string A string B string C  int N)  {  int INTSIZE = 31;  int ans = 0;  int i = 0;  while (N > 0) {  // Considering only 31 bits  int a = Convert.ToInt32(  A.Substring(i * INTSIZE  Math.Min(INTSIZE N))  2);  int b = Convert.ToInt32(  B.Substring(i * INTSIZE  Math.Min(INTSIZE N))  2);  int c = Convert.ToInt32(  C.Substring(i * INTSIZE  Math.Min(INTSIZE N))  2);  int Z = a ^ b ^ c;  // builtin function for  // counting the number of set bits.  ans += BitCount(Z);  i++;  N -= 32;  }  return ans;  }  static int BitCount(int i)  {  i = i - ((i >> 1) & 0x55555555);  i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101)  >> 24;  }  static void Main(string[] args)  {  // N represent total count of Bits  int N = 5;  string a = '10100';  string b = '00010';  string c = '10011';  Console.WriteLine(TotalFlips(a b c N));  } } 
JavaScript
function TotalFlips(A B C N) {  let INTSIZE = 31;  let ans = 0;  let i = 0;  while (N > 0)  {  // Considering only 31 bits  let a = parseInt(A.substring(i * INTSIZE Math.min(INTSIZE + i * INTSIZE N)) 2);  let b = parseInt(B.substring(i * INTSIZE Math.min(INTSIZE + i * INTSIZE N)) 2);  let c = parseInt(C.substring(i * INTSIZE Math.min(INTSIZE + i * INTSIZE N)) 2);  let Z = a ^ b ^ c;  // builtin function for  // counting the number of set bits.  ans += Z.toString(2).split('1').length - 1;  i++;  N -= 32;  }  return ans; } // Driver Code let N = 5; let a = '10100'; let b = '00010'; let c = '10011'; console.log(TotalFlips(a b c N)); 

תְפוּקָה
2

למה הקוד הזה עובד?

אנו רואים שיש להפוך את הביט אם A[i]^B[i] !=C[i]. אז נוכל לקבל את מספר ההיפוכים על ידי חישוב מספר הסיביות הקבוצתיות ב-a^b^c כאשר abc הם ייצוגים שלמים של מחרוזת בינארית. אבל אורך המחרוזת עשוי להיות גדול מ-32 בגודל מסוג int טיפוסי. אז התוכנית היא לחלק את המחרוזת למחרוזות משנה באורך 31 לבצע פעולות ולספור סיביות סט כאמור עבור כל תת מחרוזת.

מורכבות זמן: O(לוג N) כאשר לולאת ה-while פועלת עבור יומן31N פעמים וספירת סט סיביות אחראים לכל היותר O(32) עבור 32-bit ו-O(64) עבור 64-bit ולכל פעולת תת-מחרוזת O(31).

מורכבות החלל: O(1) יש לציין שלפעולת המחרוזת יש צורך ברווח O(32).

 
'
 

צור חידון