You are not logged in. Please login at www.codechef.com to post your questions!

×

TAAND - Editorial

12
7

Problem link : contest practice

Difficulty : Simple

Pre-requisites : Basic Math, Recursion, Bit Operations

Problem : Given an array find maximum AND(&) possible between any two elements.

Explanation

At first, let's consider some partial solutions.

How to get 50 points

Here you can go through each possible pair and check what AND value is. And we can find what is the maximum AND possible. Complexity of this will be O(N*N).

n=input()
arr=[]
ans=-1
for i=1 to n:
    arr[i]=input()
for i=1 to n:
    for j=i+1 to n:
        ans = max( ans, arr[i]&arr[j] )

How to get 100 points

When we are ANDing two numbers, we would like to have a 1 at the most significant bit(MSB). So, first we'll try to get a 1 at MSB. Now, suppose we denote A[i]=b_in,b_in-1...b_i0, where b_i's are the bits that could be 1 or 0.

Let's say S be the set of A[i] whose b_in is 1 and S' be the set of A[i] whose b_in is 0. If size of S ≥ 2 we are sure that our answer will be maximum if we chose a pair of numbers from S, because n'th bit of their AND will be 1 for sure. So, we know our answer lies in S.

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'.

Now, we know our answer is in S or S' and we also know n'th bit of our answer. So, our new subproblem is to find (n-1)'th bit of our answer using numbers in S or S'. We can write a recursive code for this. What will be the complexity? For each of the n bits, we'll traverse whole array to sort according to their bits. So O(n*N). We will be keeping n=30, because A[i] ≤ 109.

n=input()
arr=[]
flag[n]={}
for i=0 to n-1:
    arr[i]=input()
print foo(30)

def foo(level):  //this function will find the level'th bit
                //and accordingly return answer
    if level==-1:  // we already have solved for all bits. return 0 from here
        return 0
    Scount=0  // stores the size of set S
    ans=0 // the answer in decimal form
    for i=0 to n-1:
        if flag[i]==0:  // flag[i]=0 means arr[i] is available for us to use
            if (arr[i]&(1<<level)): // level'th bit of arr[i] is 1
                Scount++
    if Scount>=2: // our answer's level'th bit will be 1
        ans += (1<<level)
        // but we also have to set the flag of unavailable numbers
        for i=0 to n-1:
            if (arr[i]&(1<<level))==0:  // level'th bit is 0, set the flag
                flag[i]=1
    return ans+foo(level-1);  // return the current answer + answer for the next bit

Solutions : setter tester

This question is marked "community wiki".

asked 27 Jul '14, 14:47

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 03 Feb '15, 23:52

nice solution learned a lot about how to play with bits thnx man

(28 Jul '14, 17:48) ritesh_malav4★

11

Why cant you just sort an array and try updating max for every two consecutive elements? It passed to me.

link

answered 27 Jul '14, 14:54

vladamg98's gravatar image

4★vladamg98
395257
accept rate: 5%

2

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.

(27 Jul '14, 15:06) zeulb6★
1

ya this approach is wrong but it's getting accepted.

(27 Jul '14, 15:11) mrajesh0161★
1

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.

(27 Jul '14, 15:30) vladamg984★

but how will that work??
Can you pleas elaborate using an example ?

(30 Nov '14, 03:56) rishabhprsd72★

There must be some error in test cases as I did a simple sorting of numbers and took & of consecutive numbers and got an AC.But it's is wrong solution as ans for test case : 3 10 3 19 should be 3 but it will give 2. 19 = 10011 10 = 01010 3 = 00011 ANS = 3 but by sorting ANS = 2 And it's an AC code. So I think that the solutions should be rejudged. Link : http://www.codechef.com/viewsolution/4392454

link

answered 27 Jul '14, 15:12

thecodekaiser's gravatar image

5★thecodekaiser
543
accept rate: 0%

@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);
    }

}

}

(30 Aug '17, 13:41) honeysingh93★

The question says, 1 <= u < v <= N

link

answered 27 Jul '14, 15:23

ketanhwr's gravatar image

6★ketanhwr
1.9k31844
accept rate: 15%

I was bored to write a code on the formal algorithm I had developed i.e to check ranges of 2^n - where in you have to find the max range with at least two elements in that range and then compute AND operation on the closest two numbers. So instead, I checked the highest 5 elements and their AND operations with all elements and stored the max- giving AC(100) with O(10*n). Not very efficient and accurate but can be helpful in terms of saving time in contests.

http://www.codechef.com/viewsolution/4387562

link

answered 28 Jul '14, 08:31

thezodiac1994's gravatar image

6★thezodiac1994
1.0k61122
accept rate: 16%

edited 28 Jul '14, 08:33

I submitted this code in java.It gave NZEC.Can anybody tell why?

                                                                                                                                                                                                                               import java.io.BufferedReader;

                                                                                                                       import java.io.InputStreamReader;
 import java.io.PrintWriter;
import java.util.ArrayList;                                                                                                                                   import java.util.StringTokenizer;

 class AndOperation {

      long n=0;

      Integer arr[];  
                                                                                                                         public static void main(String[] args) throws Exception {


     AndOperation a=new AndOperation();

     a.solve();
   }

public void solve()throws Exception{
    long result=0;
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    PrintWriter out=new PrintWriter(System.out);
    n=Integer.parseInt(br.readLine());
    arr=new Integer[(int)n];
 long ok=0;
    if(n>=2)
        {
      for(int i=0;i<n;i++)
         arr[i]=Integer.parseInt(br.readLine());
         }
  for(int i=0;i<n;i++){
       for(int j=i+1;j<n;j++){
            ok=arr[i]& arr[j];
               if(ok>result)
                 result=ok;

               }
          }
     System.out.println(result);

     br.close();
}

}

link

answered 27 Jul '14, 15:02

mappy's gravatar image

2★mappy
1
accept rate: 0%

I have used this logic but unable to get ACCEPTED:

Sort numbers according to the range of power of 2 i.e 0-2, 2-4, 4-8, 8-16..and so on...

Now the last range in which we have at least two numbers contains those two integers

So just And the biggest two numbers in this range to get the answer

What is wrong with this?

link

answered 27 Jul '14, 15:02

mtbar131's gravatar image

2★mtbar131
163
accept rate: 0%

edited 27 Jul '14, 15:02

2

your logic fails for this test case:

4

32 31 3 3

Your output: 0

correct output:3 (because(3 (and) 3=3))...

(27 Jul '14, 15:21) prem_933★

How can we solve this problem using Trie ? I read the blog and understood the idea of finding 2 elements whose XOR is maximum using trie. But if we have to use that concept here then if a particular bit is zero in the number then either of the branch of the trie can yield optimal answer. So how to choose a specific branch ?

link

answered 27 Jul '14, 16:05

nilmish's gravatar image

2★nilmish
1614
accept rate: 0%

1

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.

(27 Jul '14, 18:00) tamimcsedu193★

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 ?

(27 Jul '14, 18:04) nilmish2★

could anybody clear the doubt asked above ?

(27 Jul '14, 21:27) wildcraft1★

@Editorialist , if you would clear the matter or tell us that it isn't possible it would be helpful. We are waiting here .

(27 Jul '14, 22:12) tamimcsedu193★

yep..wht is reasoning behind this.pls do explain .

(28 Jul '14, 00:22) wildcraft1★

If a particular bit is 0 then explore both the sub tree under it and choose the one which gives maximum value .

(29 Jul '14, 17:35) rajeshb4★
showing 5 of 6 show all

my ans uses a different approach . I just sorted the array and took and of the numbers and maintained that a&b <=max(a,b); Is my approach correct? my solution is link http://www.codechef.com/viewsolution/4386414

link

answered 27 Jul '14, 20:28

tcmandan's gravatar image

2★tcmandan
11
accept rate: 0%

my solution is easy one :)

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main(){
int n;
cin>>n;
int a[n],b[n];
for(int i=0;i<n;i++){
cin>>a[i];
b[i]=log2(a[i]);
// cout<<b[i];
}
int mx=0,temp;
std::sort(a,a+n);
std::sort(b,b+n);

for(int i=n-1;i>=0;i--){
if(b[i]==b[i-1]){
mx=max(mx,a[i]&a[i-1]);
}
}
cout<<mx<<endl;
return 0;
}
link

answered 28 Jul '14, 22:20

o007's gravatar image

4★o007
2
accept rate: 0%

push back every result into vector and sort.print the last one. it accepted.

link

answered 28 Jul '14, 22:47

mayankb_03's gravatar image

1★mayankb_03
115621
accept rate: 16%

JUST STICK TO AND DEF.(it gives the minterm i.e. & of 2 number is smaller then small of 2 numbers, so........ ) #include<stdio.h> main(void) { int n,i,j,max=0; scanf("%d",&n); int a[n]; for(i=0;i<n;i++) scanf("%d",&a[i]);

for(i=0;i<n;i++)
if (a[i]>max)
for(j=i+1;j<n;j++)
if((a[i]&a[j])>max) max=a[i]&a[j];

printf("%d",max);
return 0;
}
link

answered 18 Dec '14, 00:15

anuj_rathore's gravatar image

3★anuj_rathore
1
accept rate: 0%

what is the maths behind simply sorting the array and printing max of sum(by bitwise and) of consecutive elements. Why is there no need to test sum of non-consecutive elements?

link

answered 18 Dec '14, 11:43

mb95's gravatar image

2★mb95
1
accept rate: 0%

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]&amp;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!

link

answered 03 Jun '15, 11:37

theflash's gravatar image

3★theflash
1
accept rate: 0%

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

link

answered 22 Aug '15, 18:43

bipasha3195's gravatar image

3★bipasha3195
1
accept rate: 0%

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));
    }
link

answered 22 Dec '15, 17:47

ritan's gravatar image

2★ritan
1
accept rate: 0%

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

link
This answer is marked "community wiki".

answered 22 Feb '17, 16:26

junior_g's gravatar image

3★junior_g
444
accept rate: 0%

wikified 22 Feb '17, 16:28

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

link

answered 16 Dec '17, 21:39

adhruv1008's gravatar image

3★adhruv1008
11
accept rate: 0%

edited 16 Dec '17, 21:40

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.

link

answered 26 Jan '18, 00:17

dvjsm's gravatar image

4★dvjsm
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,725
×974
×96
×12

question asked: 27 Jul '14, 14:47

question was seen: 10,715 times

last updated: 26 Jan '18, 00:17