Maximize Bitwise AND of the array by replacing at most one element

Optimal Approach

1. The optimal approach to solve this problem is to make prefix and suffix arrays of bitwise AND.
2. We will initialize a prefix array to store the bitwise AND of array elements from the 0th element of the array and we will also initialize a suffix array which will store the bitwise AND of array elements from the nth element of the array.
3. Now, we will traverse in the loop and for every element, we will calculate the answer using this formula: ans = prefix[i-1] & suffix[i+1] 
4. We will take the maximum value of the answer and then we will return it.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// function to find the prefix array of bitwise and
vector<int> prefixAnd(int n, vector<int> a)
{
	vector<int> prefix(n);
	prefix[0] = a[0];
	for (int i = 1; i < n; i++)
	{
		prefix[i] = a[i] &prefix[i - 1];
	}
	return prefix;
}

// function to find the suffix array of bitwise and
vector<int> suffixAnd(int n, vector<int> a)
{
	vector<int> suffix(n);
	suffix[n - 1] = a[n - 1];
	for (int i = n - 2; i >= 0; i--)
	{
		suffix[i] = a[i] &suffix[i + 1];
	}
	return suffix;
}
// Function to find maximum AND by
// Replacing atmost one element by any value
int maxAnd(int n, vector<int> a, vector<int> prefix, vector< int > suffix)
{
	// To Calculate the answer
	int ans = 0;

	// Iterating through the array
	for (int i = 0; i < n; i++)
	{
		int max_and = 0XFFFFFFFF;
		if (i == 0)
		{
			max_and = max_and &suffix[i + 1];
		}
		else if (i == n - 1)
		{
			max_and = max_and &prefix[i - 1];
		}
		else
		{
			max_and = max_and &prefix[i - 1];
			max_and = max_and &suffix[i + 1];
		}
		ans = max(ans, max_and);
	}
	return ans;
}

// Driver Code
int main()
{
	int N = 4;
	vector<int> arr = { 5, 5, 7, 7 };

	vector<int> prefix = prefixAnd(N, arr);

	vector<int> suffix = suffixAnd(N, arr);

	// Function Call
	cout << maxAnd(N, arr, prefix, suffix) << endl;
}

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

Run Code

Output:

Input: {5, 5, 7, 7}      
Output: 5

Complexity Analysis

Time Complexity: O(N)

The time complexity of the above approach is O(N) because we are traversing in a for loop and we are using precomputed prefix and suffix arrays which also takes O(N) time.

Space Complexity: O(N)

The space complexity is O(N) because we are using extra space to make prefix and suffix arrays.

Read about Bitwise Operators in C here.

Frequently Asked Questions

Q1. What is 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 dynamic programming?

Ans. Dynamic programming is a technique where the problem is broken into sub-problems so that their results can be reused to obtain the optimal solution.

Key takeaways

In this article, we discussed the solution to the problem to maximize bitwise AND of the array by replacing at most one element. We hope you must have gained a better understanding of the solution to this problem.

Check out this problem - Search In Rotated Sorted Array

Until then, Keep Learning and Keep Coding and practicing on Code studio.