Maximize Bitwise AND of Array by replacing at most one element
Given an array arr[] containing N positive integers, the task is to maximize bitwise AND of the arr[] by picking at most one element of the arr[] and increment or decrement it by any value.
Examples:
Input: arr[] = {1, 2, 3}
Output: 2
Explanation: Following are the operations performed to maximize the bitwise AND of arr[]
Initially bitwise AND of {1, 2, 3} = 0
Incrementing arr[0] by 1 updates arr[] = {2, 2, 3}.
Now bitwise AND of {2, 2, 3} is 2 which is maximum possible.
Therefore, the answer is 2.Input: arr[] = {10, 10}
Output: 10
Explanation: Do not perform any operation that would be optimal.
Approach: The problem statement of this problem says to maximize AND of arr[] by replacing almost one element from arr[]. The brute force method to solve this problem is to take bitwise AND of all the elements in arr[] except one at a time and find an appropriate replacement for that element whose contribution is not added in the whole bitwise AND of arr[] each time. Do this for all the elements in arr[] and find the optimal result.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h> using namespace std; // Function to find maximum AND by // Replacing atmost one element by any value int maxAnd( int n, vector< int > a) { // To Calculate answer int ans = 0; // Iterating through the array for ( int i = 0; i < n; i++) { int max_and = 0XFFFFFFFF; // Checking and for element and // Leaving only jth element for ( int j = 0; j < n; j++) { if (i != j) { max_and = max_and & a[j]; } } // Comparing previous answers // and max answers ans = max(ans, max_and); } return ans; } // Driver Code int main() { int N = 3; vector< int > arr = { 1, 2, 3 }; // Function Call cout << maxAnd(N, arr) << "\n" ; } |
Java
import java.io.*; class GFG{ // Function to find maximum AND by // Replacing atmost one element by any value static int maxAnd( int n, int [] a) { // To Calculate answer int ans = 0 ; // Iterating through the array for ( int i = 0 ; i < n; i++) { int max_and = 0XFFFFFFFF ; // Checking and for element and // Leaving only jth element for ( int j = 0 ; j < n; j++) { if (i != j) { max_and = max_and & a[j]; } } // Comparing previous answers // and max answers ans = Math.max(ans, max_and); } return ans; } // Driver Code public static void main(String[] args) { int N = 3 ; int [] arr = { 1 , 2 , 3 }; // Function Call System.out.println( maxAnd(N, arr) ); } } // This code is contributed by Potta Lokesh |
Python
# Function to find maximum AND by # Replacing atmost one element by any value def maxAnd(n, a): # To Calculate answer ans = 0 # Iterating through the array for i in range ( 0 , n): max_and = 0XFFFFFFFF # Checking and for element and # Leaving only jth element for j in range ( 0 , n): if (i ! = j): max_and = max_and & a[j] # Comparing previous answers # and max answers ans = max (ans, max_and) return ans # Driver Code if __name__ = = '__main__' : N = 3 arr = [ 1 , 2 , 3 ] print (maxAnd(N, arr)) # This code is contributed by Samim Hossain Mondal. |
C#
using System; class GFG{ // Function to find maximum AND by // Replacing atmost one element by any value static int maxAnd( int n, int [] a) { // To Calculate answer int ans = 0; // Iterating through the array for ( int i = 0; i < n; i++) { uint max_and = 0XFFFFFFFF; // Checking and for element and // Leaving only jth element for ( int j = 0; j < n; j++) { if (i != j) { max_and = Convert.ToUInt32(max_and & a[j]); } } // Comparing previous answers // and max answers ans = Math.Max(ans, ( int )max_and); } return ans; } // Driver Code public static void Main() { int N = 3; int [] arr = { 1, 2, 3 }; // Function Call Console.Write( maxAnd(N, arr) ); } } // This code is contributed by gfgking |
Javascript
<script> // Function to find maximum AND by // Replacing atmost one element by any value const maxAnd = (n, a) => { // To Calculate answer let ans = 0; // Iterating through the array for (let i = 0; i < n; i++) { let max_and = 0XFFFFFFFF; // Checking and for element and // Leaving only jth element for (let j = 0; j < n; j++) { if (i != j) { max_and = max_and & a[j]; } } // Comparing previous answers // and max answers ans = Math.max(ans, max_and); } return ans; } // Driver Code let N = 3; let arr = [ 1, 2, 3 ]; // Function Call document.write(maxAnd(N, arr)); // This code is contributed by rakeshsahni </script> |
2
Time Complexity: O(N^2)
Auxiliary Space: O(1)