push back every result into vector and sort.print the last one.
it accepted.
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 ?
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));
}@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);
}
}
}
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.