Compruebe si algún par de arrays tiene XOR bit a bit mayor que AND bit a bit

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 ² )
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++ 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 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

# 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# 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.

<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)