Podano je zaporedje treh binarnih zaporedij A B in C z N bitov. Preštejte najmanjše število bitov, potrebnih za obračanje A in B, tako da je XOR A in B enak C. Za Primer:
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 Naiven pristop je ustvariti vse možne kombinacije bitov v A in B in jih nato uporabiti XOR, da preveri, ali je enaka C ali ne. Časovna zapletenost tega pristopa raste eksponentno, tako da ne bi bilo bolje za veliko vrednost N.
Še ena pristop je uporaba koncepta XOR.
XOR Truth Table Input Output X Y Z 0 0 - 0 0 1 - 1 1 0 - 1 1 1 - 0
Če posplošimo, bomo ugotovili, da moramo na kateri koli poziciji A in B samo obrniti ith(0 do N-1) položaj bodisi A ali B, sicer ne bomo mogli doseči najmanjšega števila bitov.
Torej na kateri koli poziciji i (0 do N-1) boste naleteli na dve vrsti situacije, tj. A[i] == B[i] ali A[i] != B[i]. Razpravljajmo o tem enega za drugim.
-
Če je A[i] == B[i], bo XOR teh bitov 0, v C[] se pojavita dva primera: C[i]==0 ali C[i]==1.
Če je C[i] == 0, bita ni treba obrniti, če pa je C[i] == 1, moramo bit obrniti v A[i] ali B[i], tako da je 1^0 == 1 ali 0^1 == 1.
-
Če A[i] != B[i], potem XOR teh bitov daje 1. V C se ponovno pojavita dva primera, tj. ali C[i] == 0 ali C[i] == 1.
Torej, če je C[i] == 1, nam ni treba obrniti bita, če pa je C[i] == 0, potem moramo obrniti bit v A[i] ali B[i], tako da je 0^0==0 ali 1^1==0
// 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>
Izhod
2
Časovna zapletenost: O(N)
Pomožni prostor: O(1)
Učinkovit pristop:
Ta pristop sledi časovni kompleksnosti O(log N).
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));
Izhod
2
Zakaj ta koda deluje?
Opazimo, da je treba bit obrniti, če je A[i]^B[i] !=C[i]. Tako lahko dobimo število obračanja z izračunom števila nastavljenih bitov v a^b^c, kjer je abc celoštevilska predstavitev binarnega niza. Toda dolžina niza je lahko večja od velikosti 32 tipičnega tipa int. Načrt je torej razdeliti niz na podnize dolžine 31, izvesti operacije in prešteti nastavljene bite, kot je omenjeno za vsak podniz.
Časovna zapletenost: O(log N) ko se zanka while izvaja za dnevnik31N-krat in štetje nastavljenih bitov predstavlja največ O(32) za 32-bitno in O(64) za 64-bitno ter za vsako operacijo podniza O(31).
Kompleksnost prostora: O(1) opozoriti je treba, da operacija podniza potrebuje O(32) prostora.
'