Encuentre el producto máximo de Bitwise AND y Bitwise OR de un subarreglo de tamaño K

Dada una array arr[] que contiene N enteros y un entero K , la tarea es encontrar el valor máximo del producto de Bitwise AND y Bitwise OR de todos los elementos de un subarreglo de tamaño K.

Ejemplo:

Entrada: arr[] = {1, 2, 3, 4}, K = 2
Salida: 6
Explicación: AND bit a bit y XOR bit a bit de todos los subarreglos de tamaño K es {(0, 3), (2, 3), ( 0, 7)} respectivamente. Por lo tanto, el valor máximo posible de su producto es 2 * 3 = 6, que es la respuesta requerida.

Entrada: arr[] = {6, 7, 7, 10, 8, 2}, K = 3
Salida: 42

Enfoque: El problema planteado se puede resolver utilizando la técnica de la ventana deslizante . La idea es mantener el valor de AND bit a bit y OR bit a bit para las ventanas de subarreglo de tamaño K, lo que se puede hacer manteniendo un arreglo que almacene el conteo de cada bit sobre todos los elementos de la ventana actual. Si la cuenta del i ^-ésimo bit es K , ese bit debe incluirse en el AND bit a bit y si la cuenta del bit es mayor que 1 , debe incluirse en el OR bit a bit. Almacenar el valor máximo de su producto sobre todas las ventanas en una variable y cuál es la respuesta requerida.

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 to convert bit array to
// decimal number representing OR
int build_or(int bit[])
{
    int ans = 0;
 
    for (int i = 0; i < 32; i++)
        if (bit[i])
            ans += (1 << i);
 
    return ans;
}
 
// Function to convert bit array to
// decimal number representing AND
int build_and(int bit[], int k)
{
    int ans = 0;
 
    for (int i = 0; i < 32; i++)
        if (bit[i] == k)
            ans += (1 << i);
 
    return ans;
}
 
// Function to find maximum value of
// AND * OR over all K sized subarrays
int maximizeAndOr(int arr[], int N, int K)
{
    // Maintain an integer array bit[]
    // of size 32 all initialized to 0
    int bit[32] = { 0 };
 
    // Create a sliding window of size k
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < 32; j++) {
            if (arr[i] & (1 << j))
                bit[j]++;
        }
    }
 
    int ans = build_and(bit, K) * build_or(bit);
 
    for (int i = K; i < N; i++) {
 
        // Perform operation for
        // removed element
        for (int j = 0; j < 32; j++) {
            if (arr[i - K] & (1 << j))
                bit[j]--;
        }
 
        // Perform operation for
        // added_element
        for (int j = 0; j < 32; j++) {
            if (arr[i] & (1 << j))
                bit[j]++;
        }
 
        // Taking maximum value
        ans = max(ans, build_and(bit, K)
                  * build_or(bit));
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int arr[] = { 6, 7, 7, 10, 8, 2 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
 
    cout << maximizeAndOr(arr, N, K);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function to convert bit array to
// decimal number representing OR
static int build_or(int[] bit)
{
    int ans = 0;
 
    for(int i = 0; i < 32; i++)
        if (bit[i] > 0)
            ans += (1 << i);
             
    return ans;
}
 
// Function to convert bit array to
// decimal number representing AND
static int build_and(int[] bit, int k)
{
    int ans = 0;
 
    for(int i = 0; i < 32; i++)
        if (bit[i] == k)
            ans += (1 << i);
 
    return ans;
}
 
// Function to find maximum value of
// AND * OR over all K sized subarrays
static int maximizeAndOr(int[] arr, int N, int K)
{
     
    // Maintain an integer array bit[]
    // of size 32 all initialized to 0
    int[] bit = new int[32];
 
    // Create a sliding window of size k
    for(int i = 0; i < K; i++)
    {
        for(int j = 0; j < 32; j++)
        {
            if ((arr[i] & (1 << j)) > 0)
                bit[j]++;
        }
    }
 
    int ans = build_and(bit, K) * build_or(bit);
 
    for(int i = K; i < N; i++)
    {
         
        // Perform operation for
        // removed element
        for(int j = 0; j < 32; j++)
        {
            if ((arr[i - K] & (1 << j)) > 0)
                bit[j]--;
        }
 
        // Perform operation for
        // added_element
        for(int j = 0; j < 32; j++)
        {
            if ((arr[i] & (1 << j)) > 0)
                bit[j]++;
        }
 
        // Taking maximum value
        ans = Math.max(ans, build_and(bit, K) *
                            build_or(bit));
    }
    return ans;
}
 
// Driver Code
public static void main(String args[])
{
    int[] arr = { 6, 7, 7, 10, 8, 2 };
    int N = arr.length;
    int K = 3;
 
    System.out.println(maximizeAndOr(arr, N, K));
}
}
 
// This code is contributed by Samim Hossain Mondal.

# Python3 program for the above approach
 
# Function to convert bit array to
# decimal number representing OR
def build_or(bit):
     
    ans = 0
 
    for i in range(0, 32):
        if (bit[i]):
            ans += (1 << i)
 
    return ans
 
# Function to convert bit array to
# decimal number representing AND
def build_and(bit, k):
 
    ans = 0
 
    for i in range(0, 32):
        if (bit[i] == k):
            ans += (1 << i)
 
    return ans
 
# Function to find maximum value of
# AND * OR over all K sized subarrays
def maximizeAndOr(arr, N, K):
 
    # Maintain an integer array bit[]
    # of size 32 all initialized to 0
    bit = [0 for _ in range(32)]
 
    # Create a sliding window of size k
    for i in range(0, K):
        for j in range(0, 32):
            if (arr[i] & (1 << j)):
                bit[j] += 1
 
    ans = build_and(bit, K) * build_or(bit)
 
    for i in range(K, N):
 
        # Perform operation for
        # removed element
        for j in range(0, 32):
            if (arr[i - K] & (1 << j)):
                bit[j] -= 1
 
        # Perform operation for
        # added_element
        for j in range(0, 32):
            if (arr[i] & (1 << j)):
                bit[j] += 1
 
        # Taking maximum value
        ans = max(ans, build_and(bit, K) *
                       build_or(bit))
 
    return ans
 
# Driver Code
if __name__ == "__main__":
 
    arr = [ 6, 7, 7, 10, 8, 2 ]
    N = len(arr)
    K = 3
 
    print(maximizeAndOr(arr, N, K))
 
# This code is contributed by rakeshsahni

// C# program for the above approach
using System;
class GFG
{
   
    // Function to convert bit array to
    // decimal number representing OR
    static int build_or(int[] bit)
    {
        int ans = 0;
 
        for (int i = 0; i < 32; i++)
            if (bit[i] > 0)
                ans += (1 << i);
 
        return ans;
    }
 
    // Function to convert bit array to
    // decimal number representing AND
    static int build_and(int[] bit, int k)
    {
        int ans = 0;
 
        for (int i = 0; i < 32; i++)
            if (bit[i] == k)
                ans += (1 << i);
 
        return ans;
    }
 
    // Function to find maximum value of
    // AND * OR over all K sized subarrays
    static int maximizeAndOr(int[] arr, int N, int K)
    {
        // Maintain an integer array bit[]
        // of size 32 all initialized to 0
        int[] bit = new int[32];
 
        // Create a sliding window of size k
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < 32; j++) {
                if ((arr[i] & (1 << j)) > 0)
                    bit[j]++;
            }
        }
 
        int ans = build_and(bit, K) * build_or(bit);
 
        for (int i = K; i < N; i++) {
 
            // Perform operation for
            // removed element
            for (int j = 0; j < 32; j++) {
                if ((arr[i - K] & (1 << j)) > 0)
                    bit[j]--;
            }
 
            // Perform operation for
            // added_element
            for (int j = 0; j < 32; j++) {
                if ((arr[i] & (1 << j)) > 0)
                    bit[j]++;
            }
 
            // Taking maximum value
            ans = Math.Max(ans, build_and(bit, K)
                                    * build_or(bit));
        }
 
        return ans;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 6, 7, 7, 10, 8, 2 };
        int N = arr.Length;
        int K = 3;
 
        Console.WriteLine(maximizeAndOr(arr, N, K));
    }
}
 
// This code is contributed by ukasp.

<script>
 
// JavaScript program to implement
// the above approach
 
// Function to convert bit array to
// decimal number representing OR
function build_or(bit)
{
    let ans = 0;
 
    for(let i = 0; i < 32; i++)
        if (bit[i])
            ans += (1 << i);
 
    return ans;
}
 
// Function to convert bit array to
// decimal number representing AND
function build_and(bit, k)
{
    let ans = 0;
 
    for(let i = 0; i < 32; i++)
        if (bit[i] == k)
            ans += (1 << i);
 
    return ans;
}
 
// Function to find maximum value of
// AND * OR over all K sized subarrays
function maximizeAndOr(arr, N, K)
{
     
    // Maintain an integer array bit[]
    // of size 32 all initialized to 0
    let bit = new Array(32).fill(0);
 
    // Create a sliding window of size k
    for(let i = 0; i < K; i++)
    {
        for(let j = 0; j < 32; j++)
        {
            if (arr[i] & (1 << j))
                bit[j]++;
        }
    }
 
    let ans = build_and(bit, K) * build_or(bit);
 
    for(let i = K; i < N; i++)
    {
         
        // Perform operation for
        // removed element
        for(let j = 0; j < 32; j++)
        {
            if (arr[i - K] & (1 << j))
                bit[j]--;
        }
 
        // Perform operation for
        // added_element
        for(let j = 0; j < 32; j++)
        {
            if (arr[i] & (1 << j))
                bit[j]++;
        }
 
        // Taking maximum value
        ans = Math.max(ans, build_and(bit, K) *
                            build_or(bit));
    }
    return ans;
}
 
// Driver Code
let arr = [ 6, 7, 7, 10, 8, 2 ];
let N = arr.length;
let K = 3;
 
document.write(maximizeAndOr(arr, N, K));
 
// This code is contributed by Potta Lokesh
 
</script>

42

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