Not so much to do! simply sort the numbers and run a loop to find the maximum if AND of consecutive numbers And that gives you the answer.Here is the code for it:
#include<bits/stdc++.h>
int main()
{ios_base::sync_with_stdio(false);
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
int max=-1;
for(int i=0;i<n-1;i++)
{
int t=a[i]&a[i+1];
if(t>max)
max=t;
}
cout<<max;
return 0;
}
It is 100 points submission…now the logic:
Rather than running an O(n^2) algo you have many things to keep in mind.
1.Bigger numbers when ANDed will provide big results(generally).
2.A big and a small number will provide small results(most of the times)
3.So better not to find all nC2 pairs but compute from the consecutive pairs and get the solution.
HOPE IT HELPS!
So i used the logic, for every number calculate the position of set bit and for that bit keep the record of two max numbers, for eg: in 2, 8, 10, a record will be kept for 8 and 10 for bit position 2. Keep a record of the max bit position where more than two elements have set bit for that particular bit position. Now print (arr[maxn][0] & arrmaxn) where maxn is highest bit power and 0 and two are the highest elements for that particular bit.
My solution passed for subtask 1 when i used set, but it doesnt pass anymore when i use array with the same logic.
Please review my code
the set of test cases for this question is not exhaustive, if u see my algorithm, u can get 100 points for the question but my algorithm fails in this test case -
3
85
42
21
my algorithm -
store all elements in array . sort the array. then traverse in reverse direction and compute the maximum of array[i],array[i-1]
the max will be the ans
I am getting RE(SIGSEGV) in the code - I haven’t allocated a very large amount of memory and I cannot detect any illegal memory reference made by me. I have used an iterative solution of the bit-representation logic.
Yeah,i know it is wrong, but that is first that came up to my mind, so i tried to submit it, and it passed after 3 mins of contest, so wasnt thinking more about that problem.
I can’t understand your code. , I can’t still understand the idea. I mean let’s say current bit is 0 , and this node has both left and right child. So why should we go to left ? I mean the right child also may produce the maximum ans can’t it.
Take for the example of inserting 0001,0111. Now if we try find and with 0011 now we go to left,left then what? I have got a 0 , and I could go both left and right. If we go left according to matching we get the max and is 1, but right has the answer 11.
If the current bit of the number is 1 and current node also has an edge to 1 then moving to that edge is optimal. But if the current bit of the number is 0 then how to decide which edge we must take ? How is this optimal :
“if the current node has the left/right son according to the current bit of the number you go in that son”. if the current bit is 0 and current node has both left and right son : then how is choosing the son denoting 0 is optimal ?