Minimice Array Sum reemplazando pares con (X, Y) manteniendo su OR bit a bit igual

Dada una array arr[] de tamaño N. Encuentre la suma mínima de la array después de realizar las operaciones dadas cualquier cantidad de veces:

• Seleccione dos índices diferentes i, j (1 ≤ i < j ≤ N),
• Reemplace arr[i] y arr[j] con X e Y respectivamente (X, Y>0), tal que arr[i] | array[j] = X | Y, donde | denota la operación OR bit a bit

Ejemplos:

Entrada: arr[] = {1, 3, 2}
Salida: 3
Explicación:  arr = {1, 3, 2} {OR bit a bit de los elementos del arreglo es 3.}, sum=6
Reemplace 1 y 3 con 3 y 0 como {1|3 = 3 = 3|0}.
arr = {3, 0, 2}, {OR bit a bit de los elementos de la array sigue siendo 3}, sum = 5
Reemplace 3 y 2 con 3 y 0 como {3|2 = 3 = 3|0}
arr = {3, 0 , 0} {o de todos los elementos de la array sigue siendo 3), sum= 3.
Esta es la suma mínima posible.

Entrada: arr[] = {3, 5, 6}
Salida: 7

Planteamiento: La solución al problema se basa en la siguiente observación: 

Si (arr[i], arr[j]) se reemplaza por ((arr[i] | arr[j]), 0) , el valor OR bit a bit seguirá siendo el mismo y la suma se minimizará.

Ilustración :

Considere: arr[] = {1, 3, 2}

Suma de array inicial = 6

Operación 1: Reemplazar (1, 3) con (1|3, 0):
    -> OR bit a bit de (1, 3) = 3
    -> Reemplazar 1 con valor OR bit a bit 3 y 3 con 0 respectivamente
    -> Se creará un nuevo par (3, 0), cuyo valor OR bit a bit será 3|0 = 3 (igual que el par original (1, 3)).
    -> Array actualizada: {3, 0, 2}
    -> Suma de array actualizada = 5

Operación 2: De manera similar, reemplace (3, 2) con (3 | 2, 0):
    -> OR bit a bit de (3, 2) = 3
    -> Reemplazar 3 con valor OR bit a bit 3 y 2 con 0 respectivamente
    -> Nuevo par sea ​​(3, 0), cuyo valor OR bit a bit será 3|0 = 3 (igual que el par original (3, 2)).
    -> Array actualizada: {3, 0, 0}
    -> Suma de array actualizada = 3

Ahora no se pueden realizar más operaciones y la suma de Array no se puede reducir más de 3. 

Por lo tanto, la suma final de Array minimizada será el OR bit a bit de todos los elementos de Array.

Siga los pasos que se mencionan a continuación:

• Atraviesa la array desde el principio.
• Calcule el OR bit a bit de todos los elementos de la array.
• Devuelve esto como la respuesta.

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

// C++ code to implement the approach
 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
// Function minsum() which will calculate
// the minimum sum of the given array
ll minsum(ll array[], ll n, ll sum)
{
    for (int i = 0; i < n; i++) {
 
        // Calculating the or of
        // all the elements in the array
        sum |= array[i];
    }
    return sum;
}
 
// Driver code
int main()
{
    ll array[] = { 1, 3, 2 };
 
    // Calculating the size of array
    ll n = sizeof(array) / sizeof(array[0]);
 
    // Initialising a variable sum with zero
    ll sum = 0;
   
    // Function call
    cout << minsum(array, n, sum) << "\n";
 
    return 0;
}

// JAVA code to implement the approach
import java.util.*;
class GFG
{
 
  // Function minsum() which will calculate
  // the minimum sum of the given array
  public static long minsum(long array[], long n,
                            long sum)
  {
    for (int i = 0; i < n; i++) {
 
      // Calculating the or of
      // all the elements in the array
      sum |= array[i];
    }
    return sum;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    long array[] = { 1, 3, 2 };
 
    // Calculating the size of array
    long n = array.length;
 
    // Initialising a variable sum with zero
    long sum = 0;
 
    // Function call
    System.out.println(minsum(array, n, sum));
  }
}
 
// This code is contributed by Taranpreet

# python3 code to implement the approach
 
# Function minsum() which will calculate
# the minimum sum of the given array
def minsum(array, n, sum):
 
    for i in range(0, n):
 
        # Calculating the or of
        # all the elements in the array
        sum |= array[i]
 
    return sum
 
# Driver code
if __name__ == "__main__":
 
    array = [1, 3, 2]
 
    # Calculating the size of array
    n = len(array)
 
    # Initialising a variable sum with zero
    sum = 0
 
    # Function call
    print(minsum(array, n, sum))
 
# This code is contributed by rakeshsahni

// C# code to implement the approach
using System;
public class GFG{
 
  // Function minsum() which will calculate
  // the minimum sum of the given array
  static long minsum(long[] array, long n,
                     long sum)
  {
    for (int i = 0; i < n; i++) {
 
      // Calculating the or of
      // all the elements in the array
      sum |= array[i];
    }
    return sum;
  }
 
  // Driver code
  static public void Main ()
  {
 
    long[] array = { 1, 3, 2 };
 
    // Calculating the size of array
    long n = array.Length;
 
    // Initialising a variable sum with zero
    long sum = 0;
 
    // Function call
    Console.Write(minsum(array, n, sum));
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
      // JavaScript code for the above approach
 
      // Function minsum() which will calculate
      // the minimum sum of the given array
      function minsum(array, n, sum) {
          for (let i = 0; i < n; i++) {
 
              // Calculating the or of
              // all the elements in the array
              sum |= array[i];
          }
          return sum;
      }
 
      // Driver code
      let array = [1, 3, 2];
 
      // Calculating the size of array
      let n = array.length;
 
      // Initialising a variable sum with zero
      let sum = 0;
 
      // Function call
      document.write(minsum(array, n, sum) + "<br>");
 
   // This code is contributed by Potta Lokesh
  </script>

3

 
 Complejidad de tiempo : O (N), ya que estamos usando un bucle para atravesar N veces.

Espacio auxiliar : O(1), ya que no estamos utilizando ningún espacio adicional.