### Archive

Archive for the ‘codechef’ Category

## Codechef: Find the largest AND operation result between any two elements of a given array

At first the problem looks very simple and can be solved easily in O(N^2).

#include <iostream>
using namespace std;

int main() {

int n;
cin>>n;
long data[n] ;
for(int i = 0; i < n; i++) {
cin>>data[i];

}
long max = 0;
for(int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++)
if (max < (data[i] & data[j]) )
max = (data[i] & data[j]);
}
cout<<max;
return 0;
}

But when it comes to huge data sets the solution for finding the maximum between every pair of elements is too much time consuming. A different approach is needed to find it quickly. Here we are reducing the complexity of the algorithm from O(N^2) to merely O(sizeof(long) * 8 * N). This is a good improvement for this algorithm.

#include <iostream>
using namespace std;

int main() {
int n;
cin>>n;
long data[n] ;
for(int i = 0; i < n; i++) {
cin>>data[i];
}
long res = 0;
int count = 0;
for(int i = sizeof(long) * 8; i >= 0; i--) {
count = 0;
for (int j = 0; j < n; j++) {
if ((data[j] & (res | (1 << i))) == (res | (1 << i))) {
count++;
}
if (count >= 2) {
res |= (1 << i);
break;
}
}
}
cout<<res;
return 0;
}

The above same code can be found here. http://ideone.com/W1LlV0