Biorąc pod uwagę sekwencję trzech sekwencji binarnych A B i C N bitów. Policz minimalne bity wymagane do zamiany A i B w taki sposób, aby XOR A i B było równe C. For Przykład :
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
Java vs C++
A Naiwne podejście polega na wygenerowaniu całej możliwej kombinacji bitów w A i B, a następnie wykonaniu ich XOR w celu sprawdzenia, czy jest równa C, czy nie. Złożoność czasowa tego podejścia rośnie wykładniczo, więc nie byłoby lepiej dla dużej wartości N.
Inny podejście polega na użyciu koncepcji XOR.
XOR Truth Table Input Output X Y Z 0 0 - 0 0 1 - 1 1 0 - 1 1 1 - 0
Jeśli uogólnimy, odkryjemy, że w dowolnej pozycji A i B wystarczy odwrócić it(0 do N-1) pozycji A lub B, w przeciwnym razie nie będziemy w stanie osiągnąć minimalnej liczby Bitów.
Zatem w dowolnej pozycji i (0 do N-1) napotkasz dwa rodzaje sytuacji, tj. albo A[i] == B[i] albo A[i] != B[i]. Omówmy to jeden po drugim.
-
Jeśli A[i] == B[i] to XOR tych bitów będzie wynosić 0. W C[] powstają dwa przypadki: C[i]==0 lub C[i]==1.
Jeśli C[i] == 0, to nie ma potrzeby odwracania bitu, ale jeśli C[i] == 1, to musimy odwrócić bit w A[i] lub B[i] tak, aby 1^0 == 1 lub 0^1 == 1.
-
Jeżeli A[i] != B[i] to XOR tych Bitów daje 1. W C ponownie pojawiają się dwa przypadki, tj. albo C[i] == 0 albo C[i] == 1.
Dlatego jeśli C[i] == 1 to nie musimy odwracać bitu, ale jeśli C[i] == 0 to musimy odwracać bit w A[i] lub B[i] tak, aby 0^0==0 lub 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>
Wyjście
2
Złożoność czasowa: NA)
Przestrzeń pomocnicza: O(1)
Efektywne podejście:
pętla for w skrypcie powłoki
Podejście to jest zgodne ze złożonością czasową 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));
Wyjście
2
Dlaczego ten kod działa?
Zauważamy, że bit musi zostać odwrócony, jeśli A[i]^B[i] !=C[i]. Możemy więc obliczyć liczbę rzutów, obliczając liczbę ustawionych bitów w a^b^c, gdzie abc są całkowitymi reprezentacjami ciągu binarnego. Ale długość łańcucha może być większa niż 32 rozmiary typowego typu int. Plan jest więc taki, aby podzielić ciąg na podciągi o długości 31, wykonać operacje i policzyć ustawione bity, jak wspomniano dla każdego podciągu.
Złożoność czasowa: O(log N) gdy pętla while działa dla dziennika31N razy i zestaw bitów odpowiada co najwyżej O(32) dla wersji 32-bitowej i O(64) dla wersji 64-bitowej oraz dla każdej operacji na podciągu O(31).
Złożoność przestrzeni: O(1) należy zauważyć, że operacja podciągu wymaga przestrzeni O(32).
'