Find the maximum product of Bitwise AND and Bitwise OR of K-size subarray

Introduction

This blog will discuss a solution to the problem to find the maximum product of Bitwise AND and Bitwise OR of K-size subarray. We are given an array containing N integers and an integer K. Our task is to find the maximum value product of Bitwise AND and Bitwise OR of all elements of a K-sized subarray. So before we deep dive into the solution to this problem, we should first look at some examples to better understand the problem.

Sample Examples

Input - 1: 

arr[]={1, 2, 3}, K=2

Output - 1: 

6

Explanation:

The bitwise AND and bitwise OR of all K-sized subarrays is [{0, 3}, {2, 3}]; therefore, the max value is 2*3 is 6. 

Input - 2: 

arr[]={9, 5, 7, 4}, K=4 

Output - 2: 

0

Approach

This problem to find the maximum product of Bitwise AND and Bitwise OR of K-size subarray can be solved using the sliding window technique. We will maintain an array named bit[], which will store the bits of all the K elements of the current window. If the count of the Kth bit is K, then we will include it in the bitwise AND, and if the count of the bit is greater than one, then we will include it in the bitwise OR. We will store the maximum value of the product of all windows in the variable ans, and when the loop we will return ans.

Also see, Euclid GCD Algorithm

Steps of Algorithm

1. We will first create an array bit[] to store the bits of all the K of the window.
2. We will now create two different functions to calculate the bitwise AND and bitwise OR of the current window.
3. In the function to calculate the bitwise AND, we will check the count of the Kth bit if it is equal to K, then we will include it in the bitwise AND.
4. In the function to calculate the bitwise OR, we will check if the count of the bit is greater than one then we will include it in the bitwise OR.
5. Now in the main function, we will store the maximum product of the bitwise AND and bitwise OR in the variable, and after the loop is over, we will return that variable as the answer.

Implementation in C++

// C++ program to Find the maximum product of Bitwise AND and Bitwise OR of K-size subarray
#include <bits/stdc++.h>
using namespace std;

// to convert the bit array to decimal
// number representing the and value
int findAND(int bit[], int k)
{
    int ans = 0;

    for (int i = 0; i < 32; i++)
        if (bit[i] == k)
            ans += (1 << i);

    return ans;
}
// to convert the bit array to decimal
// number representing the or value
int findOR(int bit[])
{
    int ans = 0;

    for (int i = 0; i < 32; i++)
        if (bit[i])
            ans += (1 << i);

    return ans;
}

// function to find the maximum value of
// product of AND and OR over all K size subarrays
int findMaximum(int arr[], int N, int K)
{
    // bit array of size 32
    int bit[32] = {};

    // 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 andValue = findAND(bit, K);
    int orValue = findOR(bit);
    int ans = andValue * orValue;

    // performing sliding window on rest of the elements of the array
    for (int i = K; i < N; i++)
    {

        // removing bits of the removed element
        for (int j = 0; j < 32; j++)
        {
            if (arr[i - K] & (1 << j))
                bit[j]--;
        }

        // adding bits of the added element
        for (int j = 0; j < 32; j++)
        {
            if (arr[i] & (1 << j))
                bit[j]++;
        }

        // storing the maximum value
        orValue = findOR(bit);
        andValue = findAND(bit, K);
        ans = max(ans, orValue * andValue);
    }

    return ans;
}

// Driver Code to Find the maximum product of Bitwise AND and Bitwise OR of K-size subarray
int main()
{
    int arr[] = {8, 3, 7, 5, 9};
    int N = 5;
    int K = 3;

    cout << findMaximum(arr, N, K);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Input: {8, 3, 7, 5, 9}, K=3     
Output: 15

Complexity Analysis

Time Complexity: O(N*log(N))

The time complexity will be O(N*(32)) but for large values of N, we can consider this approximately equal to log(N) therefore the time complexity will be O(N*log(N)).

Space Complexity: O(1)

Since no extra data structure is used therefore the space complexity will be O(1).