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