Dota trīs N bitu bināro secību A B un C secība. Saskaitiet minimālos bitus, kas nepieciešami, lai pārslēgtu A un B tā, lai A un B XOR būtu vienāds ar C. Piemērs :
watchcartoononline.io alternatīvas
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 Naiva pieeja ir ģenerēt visas iespējamās bitu kombinācijas A un B un pēc tam XOR tos pārbaudīt, lai pārbaudītu, vai tas ir vienāds ar C vai nē. Laika sarežģītība šī pieeja pieaug eksponenciāli, tāpēc tā nebūtu labāka lielai N vērtībai.
Cits pieeja ir izmantot XOR jēdzienu.
XOR Truth Table Input Output X Y Z 0 0 - 0 0 1 - 1 1 0 - 1 1 1 - 0
Ja mēs vispārinām, mēs atklāsim, ka jebkurā A un B pozīcijā mums vienkārši ir jāapgriež ith(0 līdz N-1) pozīcija A vai B, pretējā gadījumā mēs nevarēsim sasniegt minimālo bitu skaitu.
Tātad jebkurā i pozīcijā (no 0 līdz N-1) jūs saskarsities ar divu veidu situācijām, t.i., vai nu A[i] == B[i] vai A[i] != B[i]. Apspriedīsim to pa vienam.
-
Ja A[i] == B[i], tad šo bitu XOR būs 0, C[] rodas divi gadījumi: C[i]==0 vai C[i]==1.
Ja C[i] == 0, tad bits nav jāapgriež, bet, ja C[i] == 1, tad bits ir jāapgriež vai nu A[i], vai B[i], lai 1^0 == 1 vai 0^1 == 1.
-
Ja A[i] != B[i], tad šo bitu XOR dod 1 C gadījumā atkal rodas divi gadījumi, t.i., vai nu C[i] == 0 vai C[i] == 1.
Tāpēc, ja C[i] == 1, mums nav jāapgriež bits, bet, ja C[i] == 0, tad mums ir jāapgriež bits vai nu A[i] vai B[i], lai 0^0==0 vai 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>
Izvade
2
Laika sarežģītība: O(N)
Palīgtelpa: O(1)
Efektīva pieeja:
Šī pieeja atbilst O (log N) laika sarežģītībai.
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));
Izvade
2
Kāpēc šis kods darbojas?
Mēs novērojam, ka bits ir jāapgriež, ja A[i]^B[i] !=C[i]. Tātad mēs varam iegūt apvērsumu skaitu, aprēķinot iestatīto bitu skaitu a^b^c, kur abc ir binārās virknes veseli skaitļi. Taču virknes garums var būt lielāks par tipiskā int veida 32 izmēru. Tātad plāns ir sadalīt virkni apakšvirknēs, kuru garums ir 31, veikt darbības un saskaitīt kopas bitus, kā minēts katrai apakšvirknei.
Laika sarežģītība: O(log N) jo cilpa while darbojas žurnālam31N reizes un skaitīšanas kopas biti veido ne vairāk kā O(32) 32 bitiem un O(64) 64 bitiem un katrai apakšvirknes darbībai O(31).
Kosmosa sarežģītība: O(1) Jāatzīmē, ka apakšvirknes darbībai ir nepieciešama vieta O(32).
'