نظرا لتسلسل من ثلاثة تسلسلات ثنائية 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++ 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).
ما هو جافا مزدوج
'