ya this approach is wrong but it’s getting accepted.
1 Like
your logic fails for this test case:
4
32 31 3 3
Your output: 0
correct output:3 (because(3 (and) 3=3))…
2 Likes
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.
1 Like
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.
1 Like
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 ?
could anybody clear the doubt asked above ?
@Editorialist , if you would clear the matter or tell us that it isn’t possible it would be helpful. We are waiting here .
yep…wht is reasoning behind this.pls do explain .
nice solution learned a lot about how to play with bits thnx man
If a particular bit is 0 then explore both the sub tree under it and choose the one which gives maximum value .
but how will that work??
Can you pleas elaborate using an example ?
@thecodekaiser even I used the same approach…but my program gives the answer of your test case as 3 only.
Here is the code.
public class TAAND {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int n = s.nextInt();
long[] arr = new long[n];
for (int i = 0; i < n; i++) {
arr[i] = s.nextLong();
}
Arrays.sort(arr);
if(arr[arr.length-1]==0){
System.out.println("0");
}else if(arr[arr.length-1]==1){
if(arr[arr.length-2]==1){
System.out.println("1");
}else{
System.out.println("0");
}
}else {
double m = (Math.log(arr[arr.length - 1]) / Math.log(2));
int k = (int) Math.ceil(m) - 1;
ArrayList<Long> ans = new ArrayList<>();
while (k > 0) {
int count = 0;
for (int i = n - 1; i >= 0; i--) {
if ((arr[i] & (1 << k)) != 0) {
count++;
ans.add(arr[i]);
}
}
if (count > 1) {
break;
} else {
ans.clear();
}
k--;
}
System.out.println(ans);
System.out.println(k);
ans = func(ans, 1);
if (ans.size() > 1) {
System.out.println(ans.get(0) & ans.get(1));
} else {
System.out.println("0");
}
}
}
private static ArrayList<Long> func(ArrayList<Long> ans,int p) {
if(ans.size()<=2){
return ans;
}
Collections.sort(ans);
double m = (Math.log(ans.get(ans.size() - 1)) / Math.log(2));
int k = (int) Math.ceil(m)-1-p;
if(k<=0){
return ans;
}
ArrayList<Long> fina = new ArrayList<>();
for(int i =0;i<ans.size();i++){
if((ans.get(i)&(1<<k))!=0){
fina.add(ans.get(i));
}
}
if(fina.size()>1){
return func(fina,p+1);
}else{
return func(ans,p+1);
}
}
}
Best Approach
My O(n*32) solution using Trie. I just calculate the maximum AND result with the elements already present in the trie by traversing through the trie,compare it with the global maximum and then insert the current element to the trie and then move on to the next element.
public void run()
{
try
{
SReader sc=new SReader();
StringBuilder sb=new StringBuilder();
int n=sc.ni();
long arr[]=new long[n];
for(int i=0;i<n;i++)
{
arr[i]=sc.nl();
}
TrieNode root=new TrieNode();
long max=0;
for(int i=0;i<n;i++)
{
max=Math.max(max,val(root,31,arr[i]));
add(root,31,arr[i]);
}
sb.append(max);
System.out.println(sb);
}
catch(Exception e)
{
e.printStackTrace();
}
}
public static class TrieNode
{
TrieNode arr[];
TrieNode()
{
arr=new TrieNode[2];
}
}
public static void add(TrieNode node,int pos,long num)
{
if(pos==-1)
return;
int ele=((num&(1<<pos))==0)?0:1;
TrieNode nextNode=(node.arr[ele]==null)?new TrieNode():node.arr[ele];
node.arr[ele]=nextNode;
add(nextNode,pos-1,num);
}
public static long val(TrieNode node,int pos,long num)
{
if(node==null||pos==-1)
return 0;
int ele=((num&(1<<pos))==0)?0:1;
if(node.arr[ele]==null)
{
return val(node.arr[1-ele],pos-1,num);
}
return ((long)ele*1L<<pos)+val(node.arr[ele],pos-1,num);
}#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int cmpfunc(const void a,const void b){
return ((int)b-(int)a);
}
int main()
{
int n,num,count,max=0;
scanf("%d",&n);
int a[n],another;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
qsort(a,n,sizeof(int),cmpfunc);
for(int i=30;i>=0;i--)
{
num=pow(2,i),count=0;
for(int j=0;j<n;j++)
{
if(num&a[j])count++;
}
if(count>1)
{
if(max==0)
{
max+=num;
}
else
{
another=0;
for(int j=0;j<n;j++)
{
if(((a[j]&num)==num)&((a[j]&max)==max))another++;
}
if(another>1)
{
max+=num;
}
}
}
}
printf("%d",max);
}
this is simplest one & correct approach .
but this is wrong approch …for say if numbers are 7 ,8 ,23 …your answer will be 0 but correct answer is 7.
I have used the logic to get only the first two big numbers a > b (strictly greater), for numbers categorized by no. of digits in their binary representations (didn’t sort it). And also if 11011 is a candidate for digits = 5, have validated the same for 1011, 011, 11, 1 for digits = 4,3,2,1 respectively for the single number 11011. Same has been followed for all the numbers. Now trying to take the And of all the top two numbers in no.of bits from 1 to 32 passed the first set, but gave WA for the second set and not TLE. Can someone tell me what is wrong with this approach?
I think there should be a correction in the editorial, where it says -
However, if size of S is less than 2, we can never have n’th bit 1 in our answer. So, we’ll have to continue with n’th bit as 0. Note that our answer will now be in S’.
Correction - Note that our answer will now be in union of S and S’.
because, if size of S=1, the number included in S can too contribute in max AND value.
Example -
3 → 11
1 → 01
0 → 00
After checking MSB, set S = {3} and S’ = {0,1}. Now, If we don’t follow the correction, we will not be considering the number is S for 0-th bit, and will get ans=0, whereas correct ans=1 by taking bitwise AND of 3 and 1.
no , the code is right , u can get the ans by sorting because when u sorted then the difference between two side integers is less means means there is much difference between two integers the diffencce is in smaller bits so , u get the maximum ans .
btw the ans of test case 7 , 8 , 23 is 0 .
7&8 , 8&23 , 7&23 every ans is 0 .