Why cant you just sort an array and try updating max for every two consecutive elements?
It passed to me.
13 Likes
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();
}
}
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?
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 : CodeChef: Practical coding for everyone
3 Likes
The question says, 1 <= u < v <= N
1 Like
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 ?
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 CodeChef: Practical coding for everyone
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.
1 Like
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;
}
1 Like
push back every result into vector and sort.print the last one.
it accepted.
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;
}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?
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
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));
}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.
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