Maximizar el OR bit a bit de una array

Dada una array de N enteros. El OR bit a bit de todos los elementos de la array debe maximizarse realizando una tarea. La tarea es multiplicar cualquier elemento de la array como máximo k veces con un número entero x.
Ejemplos: 
 

Entrada: a = {1, 1, 1}, k = 1, x = 2 
Salida: 3 
Explicación: cualquier elección posible de hacer un elemento 
de la array dará como resultado los mismos tres números 1, 1, 2. 
Entonces, el resultado es 1 | 1 | 2 = 3.
Entrada: a = {1, 2, 4, 8}, k = 2, x = 3 
Salida: 79
 

Enfoque: precalcule las arrays OR de prefijo y sufijo. 
En una iteración, multiplique un elemento con x^k y hágalo Bitwise OR con el prefijo OR, es decir, Bitwise OR de todos los elementos anteriores y el sufijo OR, es decir, Bitwise OR de todos los elementos siguientes y devuelva el valor máximo después de todas las iteraciones.
 

// C++ program to maximize the Bitwise
// OR Sum in given array
#include <bits/stdc++.h>
using namespace std;
 
// Function to maximize the bitwise
// OR sum
int maxOR(long long arr[], int n, int k, int x)
{
    long long preSum[n + 1], suffSum[n + 1];
    long long res, pow = 1;
 
    // Compute x^k
    for (int i = 0; i < k; i++)
        pow *= x;
 
    // Find prefix bitwise OR
    preSum[0] = 0;
    for (int i = 0; i < n; i++)
        preSum[i + 1] = preSum[i] | arr[i];
 
    // Find suffix bitwise OR
    suffSum[n] = 0;
    for (int i = n - 1; i >= 0; i--)
        suffSum[i] = suffSum[i + 1] | arr[i];
 
    // Find maximum OR  value
    res = 0;
    for (int i = 0; i < n; i++)
        res = max(res, preSum[i] | (arr[i] * pow) | suffSum[i + 1]);
 
    return res;
}
 
// Drivers code
int main()
{
    long long arr[] = { 1, 2, 4, 8 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 2, x = 3;
 
    cout << maxOR(arr, n, k, x) << "\n";
 
    return 0;
}

// Java program to maximize the Bitwise
// OR Sum in given array
import java.io.*;
 
class GFG {
     
    // Function to maximize the bitwise OR sum
    public static long maxOR(long arr[], int n,
                                  int k, int x)
    {
        long preSum[] = new long[n + 1];
        long suffSum[] = new long[n + 1];
        long res = 0, pow = 1;
 
        // Compute x^k
        for (int i = 0; i < k; i++)
            pow *= x;
 
        // Find prefix bitwise OR
        preSum[0] = 0;
        for (int i = 0; i < n; i++)
            preSum[i + 1] = preSum[i] | arr[i];
 
        // Find suffix bitwise OR
        suffSum[n] = 0;
        for (int i = n - 1; i >= 0; i--)
            suffSum[i] = suffSum[i + 1] | arr[i];
 
        // Find maximum OR value
        res = 0;
        for (int i = 0; i < n; i++)
            res = Math.max(res, preSum[i] |
                (arr[i] * pow) | suffSum[i + 1]);
 
        return res;
    }
 
    // Drivers code
    public static void main(String args[])
    {
        long arr[] = { 1, 2, 4, 8 };
        int n = 4;
        int k = 2, x = 3;
         
        long ans = maxOR(arr, n, k, x);
        System.out.println(ans);
    }
}
 
// This code is contributed by Jaideep Pyne

# Python3 program to maximize the Bitwise
# OR Sum in given array
 
# Function to maximize the bitwise
# OR sum
def maxOR(arr, n, k, x):
 
    preSum = [0] * (n + 1)
    suffSum = [0] * (n + 1)
    pow = 1
 
    # Compute x^k
    for i in range(0 ,k):
        pow *= x
 
    # Find prefix bitwise OR
    preSum[0] = 0
    for i in range(0, n):
        preSum[i + 1] = preSum[i] | arr[i]
 
    # Find suffix bitwise OR
    suffSum[n] = 0
    for i in range(n-1, -1, -1):
        suffSum[i] = suffSum[i + 1] | arr[i]
 
    # Find maximum OR value
    res = 0
    for i in range(0 ,n):
        res = max(res, preSum[i] |
           (arr[i] * pow) | suffSum[i + 1])
 
    return res
 
# Drivers code
arr = [1, 2, 4, 8 ]
n = len(arr)
k = 2
x = 3
print(maxOR(arr, n, k, x))
 
# This code is contributed by Smitha

// C# program to maximize the Bitwise
// OR Sum in given array
using System;
 
class GFG {
     
    // Function to maximize the bitwise OR sum
    public static long maxOR(long []arr, int n,
                                  int k, int x)
    {
        long []preSum = new long[n + 1];
        long []suffSum = new long[n + 1];
        long res = 0, pow = 1;
 
        // Compute x^k
        for (int i = 0; i < k; i++)
            pow *= x;
 
        // Find prefix bitwise OR
        preSum[0] = 0;
        for (int i = 0; i < n; i++)
            preSum[i + 1] = preSum[i] | arr[i];
 
        // Find suffix bitwise OR
        suffSum[n] = 0;
        for (int i = n - 1; i >= 0; i--)
            suffSum[i] = suffSum[i + 1] | arr[i];
 
        // Find maximum OR value
        res = 0;
        for (int i = 0; i < n; i++)
            res = Math.Max(res, preSum[i] |
                (arr[i] * pow) | suffSum[i + 1]);
 
        return res;
    }
 
    // Drivers code
    public static void Main()
    {
        long []arr = { 1, 2, 4, 8 };
        int n = 4;
        int k = 2, x = 3;
         
        long ans = maxOR(arr, n, k, x);
        Console.Write(ans);
    }
}
 
// This code is contributed by Smitha

<?php
// PHP program to maximize the
// Bitwise OR Sum in given array
 
// Function to maximize
// the bitwise OR sum
 
function maxOR($arr, $n, $k, $x)
{
    $res; $pow = 1;
 
    // Compute x^k
    for ($i = 0; $i < $k; $i++)
        $pow *= $x;
 
    // Find prefix bitwise OR
    $preSum[0] = 0;
    for ($i = 0; $i < $n; $i++)
        $preSum[$i + 1] = $preSum[$i] |    
                              $arr[$i];
 
    // Find suffix bitwise OR
    $suffSum[$n] = 0;
    for ($i = $n - 1; $i >= 0; $i--)
        $suffSum[$i] = $suffSum[$i + 1] |
                                $arr[$i];
 
    // Find maximum OR value
    $res = 0;
    for ($i = 0; $i < $n; $i++)
        $res = max($res, $preSum[$i] |
                   ($arr[$i] * $pow) |
                    $suffSum[$i + 1]);
 
    return $res;
}
 
// Driver Code
$arr = array(1, 2, 4, 8);
$n = sizeof($arr);
$k = 2; $x = 3;
 
echo maxOR($arr, $n, $k, $x),"\n";
 
// This code is contributed by jit_t
?>

<script>
    // Javascript program to maximize the Bitwise OR Sum in given array
     
    // Function to maximize the bitwise OR sum
    function maxOR(arr, n, k, x)
    {
        let preSum = new Array(n + 1);
        let suffSum = new Array(n + 1);
        let res = 0, pow = 1;
   
        // Compute x^k
        for (let i = 0; i < k; i++)
            pow *= x;
   
        // Find prefix bitwise OR
        preSum[0] = 0;
        for (let i = 0; i < n; i++)
            preSum[i + 1] = preSum[i] | arr[i];
   
        // Find suffix bitwise OR
        suffSum[n] = 0;
        for (let i = n - 1; i >= 0; i--)
            suffSum[i] = suffSum[i + 1] | arr[i];
   
        // Find maximum OR value
        res = 0;
        for (let i = 0; i < n; i++)
            res = Math.max(res, preSum[i] | (arr[i] * pow) | suffSum[i + 1]);
   
        return res;
    }
     
    let arr = [ 1, 2, 4, 8 ];
    let n = 4;
    let k = 2, x = 3;
 
    let ans = maxOR(arr, n, k, x);
    document.write(ans);
 
// This code is contributed by suresh07.
</script>

79