Archive for the ‘codechef’ Category

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

July 27, 2014
Leave a comment

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

Categories: codechef, Programming, Technology, Uncategorized
algorithm, array, codechef