N 비트로 구성된 3개의 이진 시퀀스 A B 및 C의 시퀀스가 주어집니다. A와 B의 XOR이 C와 같도록 A와 B를 뒤집는 데 필요한 최소 비트를 계산합니다. 예 :
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와 B의 가능한 모든 비트 조합을 생성한 다음 이를 XOR하여 C와 같은지 여부를 확인하는 것입니다. 시간 복잡도 이 접근 방식은 기하급수적으로 증가하므로 N 값이 큰 경우에는 좋지 않습니다.
또 다른 접근 방식은 XOR 개념을 사용하는 것입니다.
XOR Truth Table Input Output X Y Z 0 0 - 0 0 1 - 1 1 0 - 1 1 1 - 0
일반화하면 A와 B의 어느 위치에서나 i만 뒤집으면 된다는 것을 알 수 있습니다.일(0 ~ N-1) 위치는 A 또는 B입니다. 그렇지 않으면 최소 비트 수를 달성할 수 없습니다.
따라서 i(0 ~ N-1)의 모든 위치에서 두 가지 유형의 상황, 즉 A[i] == B[i] 또는 A[i] != B[i]에 직면하게 됩니다. 하나씩 토론해보자.
-
A[i] == B[i]이면 이들 비트의 XOR은 0이 됩니다. C[]에서 두 가지 경우가 발생합니다: C[i]==0 또는 C[i]==1.
C[i] == 0이면 비트를 뒤집을 필요가 없지만 C[i] == 1이면 A[i] 또는 B[i]에서 비트를 뒤집어 1^0 == 1 또는 0^1 == 1이 되도록 해야 합니다.
-
A[i] != B[i]이면 이 비트의 XOR은 C에 1을 제공합니다. 즉, C[i] == 0 또는 C[i] == 1 중 하나가 다시 발생합니다.
따라서 C[i] == 1이면 비트를 뒤집을 필요가 없지만 C[i] == 0이면 A[i] 또는 B[i]에서 비트를 뒤집어 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)
효율적인 접근 방식:
이 접근 방식은 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));
산출
2
이 코드가 작동하는 이유는 무엇입니까?
A[i]^B[i] !=C[i]인 경우 비트를 뒤집어야 한다는 것을 알 수 있습니다. 따라서 a^b^c에서 설정된 비트 수를 계산하여 뒤집기 횟수를 얻을 수 있습니다. 여기서 abc는 이진 문자열의 정수 표현입니다. 그러나 문자열 길이는 일반적인 int 유형의 32 크기보다 클 수 있습니다. 따라서 계획은 문자열을 길이 31의 하위 문자열로 나누고 작업을 수행하고 각 하위 문자열에 대해 언급된 대로 세트 비트를 계산하는 것입니다.
시간 복잡도: 오(로그N) while 루프가 로그에 대해 실행됨에 따라31N회 및 카운팅 세트 비트는 32비트의 경우 최대 O(32), 64비트의 경우 O(64) 및 각 하위 문자열 연산 O(31)을 차지합니다.
공간 복잡도: 오(1) 하위 문자열 작업에는 O(32) 공간이 필요합니다.
'