ANDORUNI - Editorial

PROBLEM LINK:

Practice
Div1
Div2
Div3

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

DIFFICULTY:

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){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,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;
    
    t = readIntLn(1,MAX_T);

    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. :slight_smile:

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 :slight_smile: 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

35 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 number;

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

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