Дат низ од три бинарне секвенце А Б и Ц од Н битова. Избројите минималне битове потребне за окретање у А и Б тако да је КСОР за А и Б једнако Ц. За Пример:
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
А Наивни приступ је генерисање свих могућих комбинација битова у А и Б и затим њихово КСОР да би се проверило да ли је једнако Ц или не. Временска сложеност овог приступа расте експоненцијално тако да не би било боље за велику вредност Н.
Други приступ је коришћење концепта КСОР.
XOR Truth Table Input Output X Y Z 0 0 - 0 0 1 - 1 1 0 - 1 1 1 - 0
Ако генерализујемо, открићемо да на било којој позицији А и Б треба само да окренемо итх(0 до Н-1) позиције А или Б у супротном нећемо моћи да постигнемо минимални број битова.
Дакле, на било којој позицији од и (0 до Н-1) наићи ћете на две врсте ситуације, тј. или А[и] == Б[и] или А[и] != Б[и]. Хајде да о томе разговарамо један по један.
-
Ако је А[и] == Б[и] онда ће КСОР ових битова бити 0 два случаја се јављају у Ц[]: Ц[и]==0 или Ц[и]==1.
Ако је Ц[и] == 0 онда нема потребе да окрећемо бит, али ако је Ц[и] == 1 онда морамо да окренемо бит или у А[и] или Б[и] тако да је 1^0 == 1 или 0^1 == 1.
-
Ако је А[и] != Б[и] онда КСОР ових битова даје 1. У Ц се поново јављају два случаја, тј. или Ц[и] == 0 или Ц[и] == 1.
Према томе, ако је Ц[и] == 1, онда не треба да окренемо бит, али ако је Ц[и] == 0 онда морамо да окренемо бит или у А[и] или Б[и] тако да је 0^0==0 или 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>
Излаз
2
Временска сложеност: О(Н)
Помоћни простор: О(1)
Ефикасан приступ:
Овај приступ прати О(лог Н) временску сложеност.
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));
Излаз
2
Зашто овај код функционише?
Примећујемо да се бит мора окренути ако је А[и]^Б[и] !=Ц[и]. Дакле, можемо добити број преокрета израчунавањем броја постављених битова у а^б^ц где су абц целобројне репрезентације бинарног низа. Али дужина стринга може бити већа од 32 величине типичног типа инт. Дакле, план је да се стринг подели на поднизове дужине 31, изврши операције и преброји сет битова као што је поменуто за сваки подниз.
Временска сложеност: О(лог Н) док се вхиле петља покреће за лог31Н пута и број битова скупа чине највише О(32) за 32-бит и О(64) за 64-бит и за сваку операцију подниза О(31).
Сложеност простора: О(1) треба напоменути да је за операцију подниза потребно О(32) простора.
'