logo

قم بحساب الحد الأدنى من البتات لقلبها بحيث يكون XOR لـ A وB مساويًا لـ C

نظرا لتسلسل من ثلاثة تسلسلات ثنائية A B و C من N بتات. قم بحساب الحد الأدنى من البتات المطلوبة للقلب في A وB بحيث يكون XOR لـ A وB مساويًا لـ C. For مثال :  
 

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


تعقيد الوقت: على) 
المساحة المساعدة: يا(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 إجراء عمليات وحساب مجموعة البتات كما هو مذكور لكل سلسلة فرعية.

تعقيد الوقت: يا(سجل ن) أثناء تشغيل الحلقة للسجل31عدد N من المرات وعدد البتات المحددة يمثل على الأكثر O(32) لـ 32 بت وO(64) لـ 64 بت ولكل عملية سلسلة فرعية O(31).

تعقيد الفضاء: يا(1) تجدر الإشارة إلى أن عملية السلسلة الفرعية تحتاج إلى مساحة O(32).

ما هو جافا مزدوج

 
'
 

إنشاء اختبار