# ANDORUNI - Editorial

Setter: Divyansh Gupta
Testers: Lavish Gupta, Tejas Pandey
Editorialist: Ajit Sharma Kasturi

SIMPLE

### PREREQUISITES:

Bitwise operations

### PROBLEM:

We are given an array of N elements. From this array, we create array B of \frac{N \cdot (N-1)}{2} elements where for every 1 \leq i \lt j \leq N, we add A_i \land A_j to B. Then, the following operations are performed until we are left with a single element:

• Let the current maximum and minimum element of array B be X and Y respectively.

• Remove X, Y and add X \lor Y to the array B.

We need to output the final element of B.

### EXPLANATION:

• The statement seems very complicated, but the important thing to notice is the bitwise operation \lor. The property of bitwise or is that if we are performing X \lor Y, bit i will be set if atleast one of bit i in X or Y is set.

• This leads us to the most crucial observation of the problem, for every bit i, if bit i is set in atleast one of B_1, B_2, \dots B_\frac{N \cdot (N-1)}{2}, then bit i will be set in the final remaining element of B when all the operations are performed. We don’t need to worry about how the operations are performed.

• For bit i to be set in atleast one element of B, we need to have atleast 2 elements in A say j and k where A_j and A_k both have bit i set. This sets the bit i in A_j \land A_k.

• Now we have the following solution, iterate over every valid bit i, count the number of elements in array A which have bit i set. If this count is greater than 1, the final answer will have bit i set else it will be unset.

### TIME COMPLEXITY:

O(N\log 10^9) for each test case.

### SOLUTION:

Editorialist's solution
#include <bits/stdc++.h>
using namespace std;

int main()
{
int tests;
cin >> tests;
while (tests--)
{
int n;
cin >> n;

vector<int> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}

vector<int> cnt(31);
for (int bit = 30; bit >= 0; bit--)
{
for (int i = 0; i < n; i++)
{
if ((1 << bit) & a[i])
cnt[bit]++;
}
}

int ans = 0;
for (int bit = 30; bit >= 0; bit--)
{
if (cnt[bit] > 1)
{
ans += (1 << bit);
}
}

cout << ans << endl;
}
return 0;
}


Setter's solution
#include<bits/stdc++.h>
#include<string>

using namespace std;

#define ll long long int
#define ld long double
#define pb push_back
#define all(v) v.begin(),v.end()
#define sz(x) ((int)(x).size())
#define deb(x) cout<< #x << '=' << x <<endl
#define MOD 1000000007
const int N = 1e5 + 5;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;

while(t--){
ll n;
cin>>n;

ll a[n];
for(int i = 0; i < n; i++){
cin>>a[i];
}

vector<ll> cnt(32);
for(int i = 0; i < n; i++){
for(ll j = 0; j < 31; j++){
if((1LL << j) & a[i]){
cnt[j]++;
}
}
}

ll ans = 0;
for(ll i = 0; i < 32; i++){
if(cnt[i] > 1){
ans += (1LL << i);
}
}

cout<<ans<<"\n";
}
return 0;
}

Tester's solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long

/*
------------------------Input Checker----------------------------------
*/

long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}

if(!(l <= x && x <= r))
{
cerr << l << ' ' << r << ' ' << x << '\n';
assert(1 == 0);
}

return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
}
long long readIntLn(long long l,long long r){
}
string readStringLn(int l,int r){
}
string readStringSp(int l,int r){
}

/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 10000;
const int MAX_N = 100000;
const int MAX_Q = 100000;
const int MAX_val = 1000000000;
const int MAX_SUM_N = 200000;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_n = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll p = 1000000007;
ll sum_nk = 0 ;

void solve()
{
int n = readIntLn(2 , MAX_N) ;
sum_n += n ;
max_n = max(max_n , n) ;

int arr[n] ;
for(int i = 0 ; i < n-1 ; i++)
arr[i] = readIntSp(0 , 1000000000) ;
arr[n-1] = readIntLn(0 , 1000000000) ;

vector<int> cnt(30) ;

for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < 30 ; j++)
if(arr[i] & (1 << j))
cnt[j]++ ;
}

int ans = 0 , curr = 1 ;
for(int i = 0 ; i < 30 ; i++)
{
if(cnt[i] > 1)
ans += curr ;
curr *= 2 ;
}
cout << ans << '\n' ;
return ;
}

signed main()
{
//fast;
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif

int t = 1;

for(int i=1;i<=t;i++)
{
solve() ;
}

assert(getchar() == -1);
assert(sum_n <= MAX_SUM_N);

cerr<<"SUCCESS\n";
cerr<<"Tests : " << t << '\n';
cerr<<"Sum of lengths : " << sum_n << '\n';
cerr<<"Maximum length : " << max_n << '\n';
// cerr << "Sum of product : " << sum_nk << '\n' ;
// cerr<<"Total operations : " << total_ops << '\n';
// cerr<<"Answered yes : " << yess << '\n';
// cerr<<"Answered no : " << nos << '\n';
}


Please comment below if you have any questions, alternate solutions, or suggestions.

11 Likes

A different approach to solve this problem :

If You notice carefully , the answer is nothing but the or of the and of all the pairs in the array .i.e

ans = (a1 & a2) | (a1 & a3 ) … | (an-1 & an)

And another thing that i found was that :

for a number x and set of numbers x1 , x2 , … xn

(x & x1) | (x & x2) | (x & x3) | … | (x & xn) turns out to be :

           x & (x1 | x2 | x3 ........... xn)


(Try proving it yourself and i think this thing can turn out to be quite useful in some of the places)

this helps us in solving for each index in O(n) time using a suffix array (of OR of the numbers)

Here is my submission :
https://www.codechef.com/viewsolution/55910990

36 Likes

### If we notice

ans = (a1 & a2) | (a1 & a3 ) … | (an-1 & an)

Here we are taking of OR of ANDs mean-

That the bits which are present in ans should be present in at least more the one element;

So what we can do - initiate ans with 0 and set all the bits that are present in more than one element ;

To find all these bits we initiate t with first element of array after that check rest elements say x, set all bits of ans that present in t AND x and after that we include (set )all the bits of x in t;

void ANDORUNI(){
int n; cin>>n;
int t ; cin>>t;
int ans =0;
for(int i =1; i<n; i++)
{
int x ; cin>>x;

ans = ans|(t&x);
t = t|x;
}
cout<<ans;
return;
}


### TIME COMPLEXITY:

O(N) for each test case.

### SPACE COMPLEXITY:

O(1)

7 Likes

This problem can be solved in linear time-

1. We need an OR array that takes OR of each element from right to left, so for an array A0-An, orArray[i] will represent OR of all elements from i to n.
//this contains OR of elements upto index
int orArray[]=new int[n];
orArray[n-1]=a[n-1];
for (int i = a.length-2; i> 0; i--) {
orArray[i]=a[i]|orArray[i+1];
}

1. Now lets suppose we’ve 4 elements a,b,c,d then our answer will be
ab+ ac+ad + bc+ bc+cd
=> a(b+c+d)+b(c+d)+cd
=> a & orArray[(index of a+1)]+b & orArray[(index of b+1)]+ c&d
// here res is result variable containing 0
//we traverse from left
for (int i = 0; i < n-2; i++) {
//after taking AND of current element with cumilative OR of elements that follow
// we take its OR with res
res|=a[i] & orArray[i+1];
}
res|=a[n-1]&a[n-2];


Java solution-
https://www.codechef.com/viewsolution/55849959

3 Likes

I just used a map instead of a vector to store the input and then did exactly what the question asked. Successfully passed all the subtasks.

CODE

1 Like

Thanx, it is very helpful.

 int l=0,k,p=0;

for(int i=n-1;i>=1;i--){
l=l|a[i];
k=a[i-1];
p=p|(k&l);
}

cout << p;

2 Likes

Nice Approach !!

1 Like

solution observation:

prerequisite

bitwise & between any 2 numbers results in a number having the bits set to 1 iff it was set in both the numbers . eg . 1101 & 1011 = 1001.

bitwise |(or) between any 2 numbers results in a number having the bits set to 1 iff it was set in atleast one of the numbers . eg . 1101 & 1011 = 1111.

solution approach:
we’re simply doing & for each element to every other element : after that we have to pick current max and current min , doing OR and replacing those two numbers with these one.

so if we observe carefully:
in the end one element would be left : and in that element only those bits will be set , such that any one of the elements of &'s that is n*(n-1)/2 elements, have that bit set.
(as we had performed |)

and that bit would only be set if there exist atleast 2 elements having this bit set (as if had performed &).

so iterate over 32 bits (31 to 0) & see in “N” elements if the bits is set in atleast two element or not.
if it is set : include this bit in answer
else ignore.

link to my solution:
https://www.codechef.com/viewsolution/55919368

2 Likes