N bitlik A B ve C şeklinde üç ikili diziden oluşan bir dizi verilmiştir. A ve B'nin XOR'u C'ye eşit olacak şekilde A ve B'yi çevirmek için gereken minimum bitleri sayın. Örnek :
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 Naif yaklaşım A ve B'deki tüm olası bit kombinasyonlarını oluşturmak ve ardından C'ye eşit olup olmadığını kontrol etmek için bunları XORlamak. Zaman karmaşıklığı Bu yaklaşımın katlanarak büyümesi, dolayısıyla N'nin büyük değeri için daha iyi olmayacaktır.
Bir diğer yaklaşım XOR kavramını kullanmaktır.
XOR Truth Table Input Output X Y Z 0 0 - 0 0 1 - 1 1 0 - 1 1 1 - 0
Genelleme yaparsak, A ve B'nin herhangi bir konumunda yalnızca i'yi çevirmemiz gerektiğini buluruz.buA veya B'nin (0'dan N-1'e) konumu aksi takdirde minimum Bit sayısına ulaşamayız.
Yani i'nin (0'dan N-1'e) herhangi bir konumunda iki tür durumla karşılaşırsınız; yani ya A[i] == B[i] ya da A[i] != B[i]. Tek tek tartışalım.
-
Eğer A[i] == B[i] ise bu bitlerin XOR'u C[]'de ortaya çıkan iki durumda 0 olacaktır: C[i]==0 veya C[i]==1.
Eğer C[i] == 0 ise biti çevirmeye gerek yoktur ama eğer C[i] == 1 ise o zaman A[i] veya B[i]'deki biti çevirmemiz gerekir, böylece 1^0 == 1 veya 0^1 == 1 olur.
-
Eğer A[i] != B[i] ise bu Bitlerin XOR'u 1 verir. C'de iki durum tekrar ortaya çıkar, yani ya C[i] == 0 ya da C[i] == 1.
Bu nedenle, eğer C[i] == 1 ise o zaman biti çevirmemize gerek yoktur, ancak eğer C[i] == 0 ise o zaman A[i] veya B[i]'deki biti çevirmemiz gerekir, böylece 0^0==0 veya 1^1==0 olur
// C++ code to count the Minimum bits in A and B #include
// 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.
# 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# 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 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. ?> <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>
Çıkış
2
Zaman Karmaşıklığı: AÇIK)
Yardımcı alan: Ç(1)
Verimli Yaklaşım:
Bu yaklaşım O(log N) zaman karmaşıklığını takip eder.
C++// C++ code to count the Minimum bits in A and B #include
// 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.
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))
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)); } }
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));
Çıkış
2
Bu kod neden çalışıyor?
A[i]^B[i] !=C[i] ise bitin çevrilmesi gerektiğini gözlemliyoruz. Böylece abc'nin ikili dizgenin tamsayı temsilleri olduğu a^b^c'deki ayarlı bitlerin sayısını hesaplayarak çevirme sayısını elde edebiliriz. Ancak dize uzunluğu tipik bir int türünün 32 boyutundan daha büyük olabilir. Dolayısıyla plan, diziyi 31 uzunluktaki alt dizilere bölerek işlemleri gerçekleştirmek ve her bir alt dizi için belirtildiği gibi ayarlanan bitleri saymaktır.
Zaman Karmaşıklığı: O(log N) while döngüsü log için çalışırken31N kez ve sayma seti bitleri, 32 bit için en fazla O(32)'yi, 64 bit için O(64)'ü ve her alt dizi işlemi O(31)'i hesaba katar.
Uzay Karmaşıklığı: Ç(1) alt dize işleminin O(32) alanına ihtiyaç duyduğuna dikkat edilmelidir.
'