Dada una array arr[] de tamaño N , la tarea es encontrar si existe un par en la array, tal que su XOR bit a bit sea mayor que su AND bit a bit, es decir , arr[i] ⊕ arr[j] > arr[i] & arr[j] , (0 ≤ i < j ≤ N-1) donde ⊕ representa el operador XOR bit a bit y & representa el operador AND bit a bit.
Ejemplos:
Entrada: arr[] = {4, 5, 8, 6}
Salida: Sí
Explicación: XOR bit a bit de 4 y 8 es 12 y AND bit a bit = 0.Entrada: arr[] = {5, 4, 7, 6}
Salida: No
Enfoque ingenuo: el enfoque de este problema es encontrar todos los pares posibles y verificar si alguno de los pares tiene XOR bit a bit mayor que AND bit a bit.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el problema se puede resolver de manera eficiente con base en la siguiente idea:
La idea se basa en la observación de que:
- El XOR bit a bit de dos bits iguales siempre es 0, es decir, 1⊕1 = 0⊕0 = 0 y el XOR de dos bits diferentes es 1.
- El AND bit a bit de dos bits iguales es el mismo que ese bit, es decir, 1⊕1 = 1 y 0⊕0 = 0 y el AND de bits diferentes es siempre 0.
Ahora, a partir de la observación anterior, se puede decir que si el MSB (bit más significativo) de dos números está en posiciones diferentes, entonces su XOR bit a bit será mayor que AND bit a bit porque.
- El MSB será el XOR de dos bits diferentes, lo que dará como resultado un bit establecido y el AND bit a bit de dos bits diferentes será un 0.
- El MSB de XOR bit a bit tendrá una potencia mayor que el MSB de AND bit a bit.
Entonces, para encontrar si tal par es posible, verifique las condiciones solo para el mínimo y el máximo de la array porque son los valores extremos de la array. Si tienen el MSB en las mismas posiciones, todos los demás entre ellos tendrán el MSB en esa posición y XOR bit a bit nunca será mayor que AND bit a bit para cualquier par. En todos los demás casos, tal par es posible.
Siga los pasos que se mencionan a continuación para implementar el enfoque:
- Inicialice Min y Max para almacenar los elementos máximo y mínimo de la array.
- Recorra la array arr[] de i = 0 a N-1:
- Almacene el elemento máximo en Max y el elemento mínimo en Min .
- Ahora verifique la cantidad de bits de conteo de Min y Max .
- Si el conteo de bits de Max ≠ el conteo de bits de Min , entonces imprima SÍ (porque entonces el MSB de Max estará en una posición diferente que el MSB de Min).
- De lo contrario, imprima NO.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach #include <bits/stdc++.h> using namespace std; // Function to count number of bit int countBit(int n) { int Count = 0; while (n) { n /= 2; Count++; } return Count; } // Function to check // if a pair is present or not bool checkPair(int* arr, int N) { int Min = INT_MAX; int Max = INT_MIN; // Find Maximum and Minimum element // of the array for (int i = 0; i < N; i++) { Min = min(Min, arr[i]); Max = max(Max, arr[i]); } // Check if max and min element have // different count of bits // then return 1 else return 0 if (countBit(Min) != countBit(Max)) return true; else return false; } // Driver Code int main() { int arr[] = { 4, 5, 8, 6 }; int N = sizeof(arr) / sizeof(arr[0]); // Function call if (checkPair(arr, N)) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
Java
// Java code to implement the above approach import java.io.*; class GFG { // Function to count number of bit public static int countBit(int n) { int Count = 0; while (n != 0) { n /= 2; Count++; } return Count; } // Function to check // if a pair is present or not public static boolean checkPair(int arr[], int N) { int Min = Integer.MAX_VALUE; int Max = Integer.MIN_VALUE; // Find Maximum and Minimum element // of the array for (int i = 0; i < N; i++) { Min = Math.min(Min, arr[i]); Max = Math.max(Max, arr[i]); } // Check if max and min element have // different count of bits // then return 1 else return 0 if (countBit(Min) != countBit(Max)) return true; else return false; } // Driver Code public static void main(String[] args) { int arr[] = { 4, 5, 8, 6 }; int N = arr.length; // Function call if (checkPair(arr, N) == true) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by Rohit Pradhan
Python3
# Python code for the above approach # Function to count number of bit import sys def countBit(n): Count = 0 while (n): n = n // 2 Count += 1 return Count # Function to check # if a pair is present or not def checkPair(arr,N): Min = sys.maxsize Max = -sys.maxsize -1 # Find Maximum and Minimum element # of the array for i in range(N): Min = min(Min, arr[i]) Max = max(Max, arr[i]) # Check if max and min element have # different count of bits # then return 1 else return 0 if (countBit(Min) != countBit(Max)): return True else: return False # Driver Code arr = [ 4, 5, 8, 6 ] N = len(arr) # Function call if (checkPair(arr, N)): print("Yes") else: print("No") # This code is contributed by shinjanpatra
C#
// C# program to implement // the above approach using System; class GFG { // Function to count number of bit public static int countBit(int n) { int Count = 0; while (n != 0) { n /= 2; Count++; } return Count; } // Function to check // if a pair is present or not public static bool checkPair(int[] arr, int N) { int Minn = Int32.MaxValue; int Maxx = Int32.MinValue; // Find Maximum and Minimum element // of the array for (int i = 0; i < N; i++) { Minn = Math.Min(Minn, arr[i]); Maxx = Math.Max(Maxx, arr[i]); } // Check if max and min element have // different count of bits // then return 1 else return 0 if (countBit(Minn) != countBit(Maxx)) return true; else return false; } // Driver Code public static void Main() { int[] arr = { 4, 5, 8, 6 }; int N = arr.Length; // Function call if (checkPair(arr, N) == true) Console.Write("Yes"); else Console.Write("No"); } } // This code is contributed by sanjoy_62.
Javascript
<script> // Javascript program for the above approach // Function to count number of bit function countBit(n) { let Count = 0; while (n != 0) { n /= 2; Count++; } return Count; } // Function to check // if a pair is present or not function checkPair(arr, N) { let Min = Number.MAX_VALUE; let Max = Number.MIN_VALUE; // Find Maximum and Minimum element // of the array for (let i = 0; i < N; i++) { Min = Math.min(Min, arr[i]); Max = Math.max(Max, arr[i]); } // Check if max and min element have // different count of bits // then return 1 else return 0 if (countBit(Min) != countBit(Max)) return true; else return false; } // Driver Code let arr = [ 4, 5, 8, 6 ]; let N = arr.length; // Function call if (checkPair(arr, N) == true) document.write("Yes"); else document.write("No"); // This code is contributed by code_hunt. </script>
Yes
Complejidad de Tiempo : O(N)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por akashjha2671 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA