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.
Naive Approach
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
Optimal Approach
3.1.
Implementation in C++
3.1.1.
Complexity Analysis
4.
Frequently Asked Questions
5.
Key takeaways
Last Updated: Mar 27, 2024

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

Introduction

This blog will discuss a solution to the problem to maximize Bitwise AND of the array by replacing at most one element. We are given an Array containing N integers; our task is to maximize the bitwise AND of the array by picking at most one element of the array and incrementing or decrementing it by any value. 

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: 

arr1[]={5, 5}

Output - 1: 

5

Explanation:

No operation is required here

 

Input - 2: 

arr[]={3, 4, 5}

Output - 2: 

4

Explanation:

Here, we will replace 3 by 4 to get the maximum bitwise and value, i.e., 4

Also see, Euclid GCD Algorithm

Naive Approach

The brute force approach to solve this problem is to take the bitwise AND of all the elements in the array except one element, and we will have to find the appropriate element by which we will replace the chosen element. We will use nested for loops to check by replacing every element of the array and by taking the maximum of the answers obtained by replacing every element. 

Implementation in C++

// Maximize Bitwise AND of the array by replacing at most one element
#include <bits/stdc++.h>
using namespace std;

// function to find maximum bitwise and
int maxAnd(int n, vector<int> arr)
{
	// to store the answer
	int i = 0, j = 0, ans = 0;

	// Iterating through the array
	for (i = 0; i < n; i++)
	{
		int max_value = 0XFFFFFFFF;

		// calculating and value for every element
		// except the current element
		j = 0;
		while (j < n)
		{
			if (i != j)
			{
				max_value = max_value &arr[j++];
			}
			else
			{
				j++;
			}
		}
		ans = max(ans, max_value);
	}
	return ans;
}

// Driver Code to Maximize Bitwise AND of the array by replacing at most one element
int main()
{
	int N = 3;
	vector<int> arr = { 3, 4, 5 };

	// Function Call
	cout << maxAnd(N, arr) << "\n";
}

 

Output:

Input: {3, 4, 5}      
Output: 4

 

Complexity Analysis

Time Complexity: O(N*N)

Since two nested loops are being used therefore time complexity will O(N*N).

Space Complexity: 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

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

 

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.


Previous article
Form a Number Using Bit Rotations of N having the Same Frequency of each Digit
Next article
Bit Stuffing and Bit Destuffing
Live masterclass