Având în vedere o secvență de trei secvențe binare A B și C de N biți. Numărați biții minimi necesari pentru a inversa în A și B astfel încât XOR al lui A și B să fie egal cu C. Pentru Exemplu:
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
O Abordare naivă este de a genera toate combinațiile posibile de biți în A și B și apoi de a le XOR pentru a verifica dacă este egal cu C sau nu. Complexitatea timpului al acestei abordări crește exponențial, așa că nu ar fi mai bine pentru o valoare mare a lui N.
Altul abordarea este utilizarea conceptului de XOR.
XOR Truth Table Input Output X Y Z 0 0 - 0 0 1 - 1 1 0 - 1 1 1 - 0
Dacă generalizăm, vom descoperi că în orice poziție a lui A și B trebuie doar să răsturnăm ith(0 la N-1) poziția fie a A sau B, altfel nu vom putea atinge numărul minim de biți.
Deci, în orice poziție a lui i (de la 0 la N-1) veți întâlni două tipuri de situații, adică fie A[i] == B[i], fie A[i] != B[i]. Să o discutăm unul câte unul.
-
Dacă A[i] == B[i] atunci XOR al acestor biți va fi 0, apar două cazuri în C[]: C[i]==0 sau C[i]==1.
Dacă C[i] == 0, atunci nu este nevoie să răsturnăm bitul, dar dacă C[i] == 1, atunci trebuie să inversăm bitul fie în A[i], fie în B[i], astfel încât 1^0 == 1 sau 0^1 == 1.
-
Dacă A[i] != B[i] atunci XOR al acestor biți dă un 1 În C apar din nou două cazuri, adică fie C[i] == 0, fie C[i] == 1.
Prin urmare, dacă C[i] == 1, atunci nu trebuie să inversăm bitul, dar dacă C[i] == 0, atunci trebuie să inversăm bitul fie în A[i], fie în B[i], astfel încât 0^0==0 sau 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>
Ieșire
2
Complexitatea timpului: PE)
Spatiu auxiliar: O(1)
Abordare eficientă:
Această abordare urmează complexitatea timpului 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));
Ieșire
2
De ce funcționează acest cod?
Observăm că bitul trebuie răsturnat dacă A[i]^B[i] !=C[i]. Deci, putem obține numărul de flip-uri calculând numărul de biți setați în a^b^c unde abc sunt reprezentări întregi ale șirului binar. Dar lungimea șirului poate fi mai mare decât dimensiunea 32 a unui tip int tipic. Deci, planul este de a împărți șirul în subșiruri de lungime 31, efectuați operații și numărați biții setați așa cum este menționat pentru fiecare subșir.
Complexitatea timpului: O(log N) deoarece bucla while rulează pentru jurnal31N ori și numărarea setului de biți reprezintă cel mult O(32) pentru 32 de biți și O(64) pentru 64 de biți și pentru fiecare operație de subșir O(31).
Complexitatea spațiului: O(1) de remarcat faptul că operația cu subșiruri necesită spațiu O(32).
'