TAAND - Editorial

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

http://pastebin.com/WvqeeZWA

Can anyone tell me what’s wrong with this code.I understand that I am making redundant vectors. But why wrong answer.
Thanks!!!

    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    #include<vector>
    #include<cmath>
    int ans;
    using namespace std;
    int recursion(vector<int> v,int n)
    {
    	if(n==-1)
    		return 0;
    	vector<int> v1;
    	vector<int> v2;
    	int size1,size2;
    	size1=size2=0;
    	for(int i=0;i<v.size();i++)
    	{
    		if((1<<n)&v[i])
    		{
    			v1.push_back(v[i]);
    			size1++;
    		}
    		else
    		{
    			v2.push_back(v[i]);
    			size2++;
    		}
    	}
    	if(size1>=2)
    	{
    		//cout<<" calling1"<<endl;
    		return (1<<n) + recursion(v1,n-1);
    	}
    	else
    	{
    		//cout<<" calling2"<<endl;
    		return recursion(v2,n-1);
    	}
    }
    int main()
    {
    	/*int n=4;
    	for(int i=0;i<18;i++)
    	{
    		cout<<((1<<n)&i) <<" ";
    	}*/
    	int n;
    	scanf("%d",&n);
    	vector<int> v(n);
    	for(int i=0;i<n;i++)
    		cin>>v[i];
    	ans=0;
    	printf("%d\n",recursion(v,32));
    }

very Weak test cases. @o007’s solution not giving right ans but got AC.

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.

Solution

I would be thankful for any help.

It should be fail on testcase like 4 2 4 8 18 as pointed by abhisheklfs in problem’s comment , really weak test even my bruteforce got accepted.

2 Likes

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. :frowning: , 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);
    }

}

}

This might help