## 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)**