Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Sample Examples
2.
Approach
2.1.
Steps of Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
4.
Key takeaways
Last Updated: Mar 27, 2024

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

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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;
}

 

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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

Q1. What is the space complexity of an algorithm?

Ans. Space complexity is the overall space taken by algorithm w.r.t input size.

 

Q2. What is time complexity?

Ans. The time complexity of an algorithm is defined as the time taken by the computer to run an algorithm.

 

Q3. What is the sliding window technique?

Ans. S sliding window is a sub-list that runs over an underlying collection. I.e., if you have an array like this,

[1 2 3 4 5 6 7]

a sliding window of size 3 would run over it like

[1 2 3]
  [2 3 4]
    [3 4 5]
      [4 5 6]
        [5 6 7]

Key takeaways

In this article, we discussed the solution to the problem to find the maximum product of bitwise AND and bitwise OR of K-size subarray. We hope you must have gained a better understanding of the solution to this problem.
Check out this problem - Maximum Product Subarray

For more such interesting problems, you can visit Code studio.


Previous article
Space optimization using bit manipulations
Next article
Find the size of the largest subset with bitwise AND greater than their bitwise XOR
Live masterclass