Encuentre el valor mínimo de la expresión dada sobre todos los pares de la array

Posted on by Rudeus Greyrat

Dada una array A de tamaño N, encuentre el valor mínimo de la expresión :  (A_i \& A_j) \o más (A_i | A_j) sobre todos los pares (i, j) (donde i != j). Aquí  \& ,  | y  \oplus representa AND bit a bit, OR bit a bit y XOR bit a bit respectivamente. 
Ejemplos: 
 

Input:  A = [1, 2, 3, 4, 5]
Output:  1
Explanation: 
(A[1] and A[2]) xor (A[1] or A[2]) = 1,
which is minimum possible value.

Input : A = [12, 3, 14, 5, 9, 8]
Output : 1

Enfoque ingenuo: 
iterar a través de todos los pares de la array con un índice diferente y encontrar el valor mínimo posible de la expresión dada sobre ellos.
Debajo de la implementación del enfoque anterior.
 

C++

// C++ program to find the minimum
// value of the given expression
// over all pairs of the array
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// value of the expression
int MinimumValue(int a[], int n)
{
 
    int answer = INT_MAX;
     
    // Iterate over all the pairs
    // and find the minimum value
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            answer = min(answer,
                         ((a[i] & a[j])
                          ^ (a[i] | a[j])));
        }
    }
    return answer;
}
// Driver code
int main()
{
    int N = 6;
    int A[N] = { 12, 3, 14, 5, 9, 8 };
 
    cout << MinimumValue(A, N);
 
    return 0;
}

Java

// Java program to find the minimum
// value of the given expression
// over all pairs of the array
import java.io.*;
import java.util.Arrays;
 
class GFG
{
 
// Function to find the minimum
// value of the expression
static int MinimumValue(int a[], int n)
{
 
    int answer = Integer.MAX_VALUE;
     
    // Iterate over all the pairs
    // and find the minimum value
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            answer = Math.min(answer, ((a[i] & a[j])
                                  ^ (a[i] | a[j])));
        }
    }
    return answer;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 6;
    int[] A = new int[]{ 12, 3, 14, 5, 9, 8 };
    System.out.print(MinimumValue(A, N));
 
}
}
 
// This code is contributed by shivanisinghss2110

Python3

# Python3 program to find the minimum
# value of the given expression
# over all pairs of the array
import sys
 
# Function to find the minimum
# value of the expression
def MinimumValue(a,n):
    answer = sys.maxsize
     
    # Iterate over all the pairs
    # and find the minimum value
    for i in range(n):
        for j in range(i + 1, n, 1):
            answer = min(answer,((a[i] & a[j])^(a[i] | a[j])))
    return answer
 
# Driver code
if __name__ == '__main__':
    N = 6
    A = [12, 3, 14, 5, 9, 8]
 
    print(MinimumValue(A, N))
 
# This code is contributed by Bhupendra_Singh

C#

// C# program to find the minimum
// value of the given expression
// over all pairs of the array
using System;
 
class GFG{
 
// Function to find the minimum
// value of the expression
static int MinimumValue(int []a, int n)
{
    int answer = Int32.MaxValue;
     
    // Iterate over all the pairs
    // and find the minimum value
    for(int i = 0; i < n; i++)
    {
       for(int j = i + 1; j < n; j++)
       {
           answer = Math.Min(answer,
                           ((a[i] & a[j]) ^
                            (a[i] | a[j])));
       }
    }
    return answer;
}
 
// Driver Code
public static void Main()
{
    int N = 6;
    int[] A = new int[]{ 12, 3, 14, 5, 9, 8 };
    Console.Write(MinimumValue(A, N));
}
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
// JavaScript program to find the minimum
// value of the given expression
// over all pairs of the array
 
// Function to find the minimum
// value of the expression
function MinimumValue(a, n)
{
 
    let answer = Number.MAX_SAFE_INTEGER;
     
    // Iterate over all the pairs
    // and find the minimum value
    for (let i = 0; i < n; i++)
    {
        for (let j = i + 1; j < n; j++)
        {
            answer = Math.min(answer,
                        ((a[i] & a[j])
                        ^ (a[i] | a[j])));
        }
    }
    return answer;
}
 
// Driver code
    let N = 6;
    let A = [ 12, 3, 14, 5, 9, 8 ];
    document.write(MinimumValue(A, N));
 
// This code is contributed by Surbhi Tyagi.
</script>
Producción: 

1

 

Tiempo Complejidad : O(N 2 )

Espacio Auxiliar: O(1)
Enfoque Eficiente 
 

  • Simplifiquemos la expresión dada:
     

+ representa O bit a bit 
. representa AND a nivel  de bits
^ representa XOR a nivel  de bits
‘ representa el complemento a 1
(x . y) ^ (x + y) = (x . y) . (x + y)’ + (x . y)’ . (x + y) (usando la definición de XOR) 
= (x . y) . (x’ . y’) + (x’+ y’) . (x + y) (ley de De morgan) 
= x.x’.y.y’ + x’.x + x’.y + y’.x + yy 
= 0 + 0 + x’.y + y’.x + 0 
= x ^ y 
 

  •  
  • Dado que la expresión se simplifica al mínimo par de valores xor, simplemente podemos usar el algoritmo mencionado en este artículo para encontrar lo mismo de manera eficiente. 
     

Debajo de la implementación del enfoque anterior.
 

C++

// C++ program to find the minimum
// value of the given expression
// over all pairs of the array
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimum
// value of the expression
int MinimumValue(int arr[], int n)
{
 
    // The expression simplifies to
    // finding the minimum xor
    // value pair
 
    // Sort given array
    sort(arr, arr + n);
 
    int minXor = INT_MAX;
    int val = 0;
 
    // Calculate min xor of
    // consecutive pairs
    for (int i = 0; i < n - 1; i++)
    {
        val = arr[i] ^ arr[i + 1];
        minXor = min(minXor, val);
    }
 
    return minXor;
}
 
// Driver code
int main()
{
    int N = 6;
    int A[N] = { 12, 3, 14, 5, 9, 8 };
 
    cout << MinimumValue(A, N);
 
    return 0;
}

Java

// Java program to find the minimum
// value of the given expression
// over all pairs of the array
import java.io.*;
import java.util.Arrays;
 
class GFG {
 
// Function to find the minimum
// value of the expression
static int MinimumValue(int arr[], int n)
{
     
    // The expression simplifies to
    // finding the minimum xor
    // value pair
    // Sort given array
    Arrays.sort(arr);
 
    int minXor = Integer.MAX_VALUE;
    int val = 0;
 
    // Calculate min xor of
    // consecutive pairs
    for(int i = 0; i < n - 1; i++)
    {
       val = arr[i] ^ arr[i + 1];
       minXor = Math.min(minXor, val);
    }
 
    return minXor;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 6;
    int[] A = new int[]{ 12, 3, 14, 5, 9, 8 };
 
    System.out.print(MinimumValue(A, N));
}
}
 
// This code is contributed by shivanisinghss2110

Python3

# Python3 program to find the minimum
# value of the given expression
# over all pairs of the array
import sys
 
# Function to find the minimum
# value of the expression
def MinimumValue(arr, n):
 
    # The expression simplifies
    # to finding the minimum
    # xor value pair
    # Sort given array
    arr.sort();
 
    minXor = sys.maxsize;
    val = 0;
 
    # Calculate min xor of
    # consecutive pairs
    for i in range(0, n - 1):
        val = arr[i] ^ arr[i + 1];
        minXor = min(minXor, val);
     
    return minXor;
 
# Driver code
if __name__ == '__main__':
     
    N = 6;
    A = [ 12, 3, 14, 5, 9, 8 ];
 
    print(MinimumValue(A, N));
     
# This code is contributed by sapnasingh4991

C#

// C# program to find the minimum
// value of the given expression
// over all pairs of the array
using System;
 
class GFG{
 
// Function to find the minimum
// value of the expression
static int MinimumValue(int []arr, int n)
{
     
    // The expression simplifies to
    // finding the minimum xor
    // value pair
    // Sort given array
    Array.Sort(arr);
 
    int minXor = Int32.MaxValue;
    int val = 0;
 
    // Calculate min xor of
    // consecutive pairs
    for(int i = 0; i < n - 1; i++)
    {
       val = arr[i] ^ arr[i + 1];
       minXor = Math.Min(minXor, val);
    }
     
    return minXor;
}
 
// Driver Code
public static void Main()
{
    int N = 6;
    int[] A = new int[]{ 12, 3, 14, 5, 9, 8 };
 
    Console.Write(MinimumValue(A, N));
}
}
 
// This code is contributed by shivanisinghss2110

Javascript

<script>
    // Javascript program to find the minimum
    // value of the given expression
    // over all pairs of the array
     
    // Function to find the minimum
    // value of the expression
    function MinimumValue(arr, n)
    {
 
        // The expression simplifies to
        // finding the minimum xor
        // value pair
 
        // Sort given array
        arr.sort();
 
        let minXor = Number.MAX_VALUE;
        let val = 0;
 
        // Calculate min xor of
        // consecutive pairs
        for (let i = 0; i < n - 1; i++)
        {
            val = arr[i] ^ arr[i + 1];
            minXor = Math.min(minXor, val);
        }
 
        return minXor;
    }
     
    let N = 6;
    let A = [ 12, 3, 14, 5, 9, 8 ];
  
    document.write(MinimumValue(A, N));
     
    //This code is contributed by divyeshrabadiya07
</script>
Producción: 

1

 

Complejidad del tiempo: O(N * log(N))

Espacio Auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por king_tsar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *