And Operation | CodeChef Solution

Hello coders, today we are going to solve And Operation CodeChef Solution whose Problem Code is TAAND.

Task

Given an array of n non-negative integers: A₁, A₂, …, A_N. Your mission is finding a pair of integers A_u, A_v (1 ≤ u < v ≤ N) such that (A_u and A_v) is as large as possible. And is a bit-wise operation which is corresponding to & in C++ and Java.

Input Format

The first line of the input contains a single integer N. The ith line in the next N lines contains the A_i.

Output Format

Contains a single integer which is the largest value of A_u and A_v where 1 ≤ u < v ≤ N.

Constraints

50 points:

• 2 ≤ N ≤ 5000
• 0 ≤ A_i ≤ 10⁹

50 points:

• 2 ≤ N ≤ 3 × 10⁵
• 0 ≤ A_i ≤ 10⁹

Example

Sample Input

4
2
4
8
10

Sample Output

8

Explanation

• 2 and 4 = 0
• 2 and 8 = 0
• 2 and 10 = 2
• 4 and 8 = 0
• 4 and 10 = 0
• 8 and 10 = 8

Solution – And Operation

C++

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n],i;
    for(i=0;i<n;i++) cin>>a[i];
    sort(a,a+n);
    int ans = INT_MIN;
    for(i=1;i<n;i++)
    ans = max(ans,a[i]&a[i-1]);
    cout<<ans;
}

Python

N = int(input())
nums = []
for n in range(N):
    nums.append(int(input()))
    
availID = [n for n in range(N)]
mask = 1 << 30
maxAnd = 0

for bit in range(30,-1,-1):
    onesID = []
    for i in availID:
        if (nums[i] & mask != 0):
            onesID.append(i)
            
    if (len(onesID) >= 2):
        maxAnd += mask
        availID = onesID[:]
    
    mask >>= 1

print(maxAnd)
        

Java

/* package codechef; // don't place package name! */

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		int arr[]=new int[N];
		int temp;
		for(int i=0;i<N;i++){
		    arr[i]=Integer.parseInt(br.readLine());
		}
		int andMax=0;
		Arrays.sort(arr);
		for(int i=0;i<N-1;i++){
		    andMax=Math.max(andMax,(arr[i]&arr[i+1]));
		}
		System.out.println(andMax);
	}
}

Disclaimer: The above Problem (And Operation) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.