Maximizar la suma de LSB de Bitwise OR de todos los N/2 pares posibles de un Array dado

Dada una array arr[] que consta de N enteros positivos, donde N es par, la tarea es formar N/2 pares de modo que la suma del Bit menos significativo de Bitwise OR de todos estos pares sea máxima.

Ejemplos:

Entrada: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Salida: 8
Explicación:
Al formar los pares como (8, 4), (6, 2), (1, 3) ,(5, 7), el OR bit a bit del par viene dado por:
8 OR 4 = 12 y LSB = 4
6 OR 2 = 6 y LSB = 2
1 OR 3 = 3 y LSB = 1
5 OR 7 = 7 y LSB = 1
La suma de todos los LSB es 4 + 2 + 1 + 1 = 8, que es la máxima suma posible.

Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 3

Enfoque: el problema dado se puede resolver encontrando el LSB de cada elemento de la array arr[i] y almacenándolos en otra array, digamos lsb_arr[] y ordenando esta array en orden descendente . Ahora, almacenar solo el LSB de cada elemento de la array es suficiente porque en la respuesta, solo se requiere considerar el LSB . Por lo tanto, solo se pueden usar los LSB para la operación OR bit a bit . Ahora, considere cada par (i, i + 1) y agregue el mínimo de estos dos al resultado. Siga los pasos a continuación para resolver el problema dado:

• Inicialice una lista lsb_arr[] para almacenar el bit menos significativo de todos los elementos de la array arr[i] .
• Recorra el rango [0, N) y almacene el LSB de cada arr[i] en lsb_arr[] .
• Ordene la lista lsb_arr[] en orden descendente .
• Inicialice la variable ans como 0 para almacenar la suma resultante de los bits menos significativos .
• Recorra el rango [0, N) usando la variable i y agregue el valor del elemento en la posición (i + 1) a la variable ans y aumente el valor de i en 2 .
• Después de completar los pasos anteriores, imprima el valor de ans como la resultante.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function top get LSB value of v
int chk(int n)
{
 
    // Binary conversion
    vector<int> v;
 
    while (n != 0) {
        v.push_back(n % 2);
        n = n / 2;
    }
 
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == 1) {
            return pow(2, i);
        }
    }
 
    return 0;
}
 
// Function to find the sum of LSBs of
// all possible pairs of the given array
void sumOfLSB(int arr[], int N)
{
 
    // Stores the LSB of array elements
    vector<int> lsb_arr;
    for (int i = 0; i < N; i++) {
 
        // Storing the LSB values
        lsb_arr.push_back(chk(arr[i]));
    }
    // Sort the array lab_arr[]
    sort(lsb_arr.begin(), lsb_arr.end(), greater<int>());
 
    int ans = 0;
 
    for (int i = 0; i < N - 1; i += 2) {
 
        // Taking pairwise sum to get
        // the maximum sum of LSB
        ans += (lsb_arr[i + 1]);
    }
 
    // Print the result
    cout << (ans);
}
 
// Driver Code
int main()
{
    int N = 5;
    int arr[] = { 1, 2, 3, 4, 5 };
 
    // Function Call
    sumOfLSB(arr, N);
}
 
// This code is contributed by Potta Lokesh

// Java program for the above approach
import java.util.*;
class GFG
{
 
// Function top get LSB value of v
static int chk(int n)
{
 
    // Binary conversion
    Vector<Integer> v = new Vector<Integer>();
 
    while (n != 0) {
        v.add(n % 2);
        n = n / 2;
    }
 
    for (int i = 0; i < v.size(); i++) {
        if (v.get(i) == 1) {
            return (int) Math.pow(2, i);
        }
    }
 
    return 0;
}
 
// Function to find the sum of LSBs of
// all possible pairs of the given array
static void sumOfLSB(int arr[], int N)
{
 
    // Stores the LSB of array elements
    Vector<Integer> lsb_arr = new Vector<Integer>() ;
    for (int i = 0; i < N; i++) {
 
        // Storing the LSB values
        lsb_arr.add(chk(arr[i]));
    }
   
    // Sort the array lab_arr[]
    Collections.sort(lsb_arr);
 
    int ans = 0;
 
    for (int i = 0; i < N - 1; i += 2) {
 
        // Taking pairwise sum to get
        // the maximum sum of LSB
        ans += (lsb_arr.get(i + 1));
    }
 
    // Print the result
    System.out.print(ans);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5;
    int arr[] = { 1, 2, 3, 4, 5 };
 
    // Function Call
    sumOfLSB(arr, N);
}
}
 
// This code contributed by shikhasingrajput

# Python program for the above approach
 
# Function top get LSB value of v
def chk(v):
 
    # Binary conversion
    v = list(bin(v)[2:])
    v.reverse()
     
    if('1' in v):
        v = v.index('1')
        return (2**v)
    else:
        return 0
 
# Function to find the sum of LSBs of
# all possible pairs of the given array
def sumOfLSB(arr, N):
 
    # Stores the LSB of array elements
    lsb_arr = []
    for i in range(N):
 
        # Storing the LSB values
        lsb_arr.append(chk(arr[i]))
 
    # Sort the array lab_arr[]
    lsb_arr.sort(reverse=True)
 
    ans = 0
 
    for i in range(0, N-1, 2):
 
        # Taking pairwise sum to get
        # the maximum sum of LSB
        ans += (lsb_arr[i+1])
 
    # Print the result
    print(ans)
 
# Driver Code
N = 5
arr = [1, 2, 3, 4, 5]
 
# Function Call
sumOfLSB(arr, N)

<script>
    // JavaScript program for the above approach
 
    // Function top get LSB value of v
    const chk = (n) => {
 
        // Binary conversion
        let v = [];
 
        while (n != 0) {
            v.push(n % 2);
            n = parseInt(n / 2);
        }
 
        for (let i = 0; i < v.length; i++) {
            if (v[i] == 1) {
                return Math.pow(2, i);
            }
        }
 
        return 0;
    }
 
    // Function to find the sum of LSBs of
    // all possible pairs of the given array
    const sumOfLSB = (arr, N) => {
 
        // Stores the LSB of array elements
        let lsb_arr = [];
        for (let i = 0; i < N; i++) {
 
            // Storing the LSB values
            lsb_arr.push(chk(arr[i]));
        }
        // Sort the array lab_arr[]
         
        lsb_arr.sort((a, b) => a - b)
        let ans = 0;
 
        for (let i = 0; i < N - 1; i += 2) {
 
            // Taking pairwise sum to get
            // the maximum sum of LSB
            ans += (lsb_arr[i + 1]);
        }
 
        // Print the result
        document.write(ans);
    }
 
    // Driver Code
    let N = 5;
    let arr = [1, 2, 3, 4, 5];
 
    // Function Call
    sumOfLSB(arr, N);
     
    // This code is contributed by rakeshsahni
</script>

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
   
// Function top get LSB value of v
static int chk(int n)
{
 
    // Binary conversion
    List<int> v = new List<int>();
 
    while (n != 0) {
        v.Add(n % 2);
        n = n / 2;
    }
     
      int j = 0;
    foreach(int i in v) {
        if (i == 1) {
            return (int) Math.Pow(2.0, (double)j);
        }
          j++;
    }
 
    return 0;
}
 
// Function to find the sum of LSBs of
// all possible pairs of the given array
static void sumOfLSB(int[] arr, int N)
{
 
    // Stores the LSB of array elements
      int[] lsb_arr = new int[N];
     
    for (int i = 0; i < N; i++) {
 
        // Storing the LSB values
        lsb_arr[i] = chk(arr[i]);
    }
   
    // Sort the array lab_arr[]
    Array.Sort(lsb_arr);
 
    int ans = 0;
 
    for (int i = 0; i < N - 1; i += 2) {
 
        // Taking pairwise sum to get
        // the maximum sum of LSB
        ans += (lsb_arr[i + 1]);
    }
 
    // Print the result
    Console.WriteLine(ans);
}
 
// Driver Code
static public void Main (){
 
    int N = 5;
    int[] arr = { 1, 2, 3, 4, 5 };
 
    // Function Call
    sumOfLSB(arr, N);
}
}
 
// This code is contributed by Dharanendra L V.

3

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)