WAND - Editorial

PROBLEM LINK:

WAND

Author: Hitk Codechef Chapter

Tester: Ankur Kayal

Editorialist: Hitk Codechef Chapter

DIFFICULTY:

MEDIUM

PREREQUISITES:

Bits Manipulation, Greedy.

PROBLEM:

You have to calculate the minimum no. of bits used to represent bitwise AND of any pair of numbers in the given array.

EXPLANATION:

In this question, Wizard has an array of integers named a. He has to find out the bitwise-AND of all the pairs of elements of the array. Before carrying out the operation, he wants to make sure that he has just enough bits to store the answer of the AND operation of any pair of numbers from the array.

So basically we want to know the maximum and value which we can get from this array taking elements pair-wise. The brute force approach would be finding all such ands and print the number of bits required to represent the maximum and value in binary, but wait how many elements do we have here??? 10^5! The number of such possibilities would be 10^10 which is over a billion. We definitely don’t want our compiler to die XD.

To avoid doing this, we create a cache which will store frequency of set bits at a particular position. We convert the number to binary, for each set bit, we increment the value of frequency [position] by 1. We know that the binary representation of 10^9 can have at most 30 bits in their binary representation. We also know that and-ing 2 bits can give 1 only if both bits are 1. So now the question gets reduced checking the frequency array from 30th pos to 1st pos and checking where frequency is greater than equal to 2.

Solving it takes time O (30*N), where N is the length of the array. When N=1, it’s a trivial case where pairwise bitwise AND is not possible so we simply print 0 and when the maximum value of pairwise bitwise AND is 0, no. of bits required to store 0 is 1 so we print 1.

SOLUTIONS:

Setter's Solution
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    bitset<31> binary[100000];
    while (t--)
    {
        //binary[100000]={};
        int n;
        cin >> n;

        unsigned long long int x;
        for (int i = 0; i < n; i++)
        {
            cin >> x;
            binary[i] &= (0ULL);
            binary[i] |= (x);
        }
        if (n == 1)
        {
            cout << "0\n";
            continue;
        }
        int i = 30, j = 0, found = 0;
        while (i >= 0 && found != 2)
        {
            found = 0;
            for (j = 0; j < n; j++)
            {
                if (binary[j].test(i))
                    ++found;
                if (found >= 2)
                {
                    cout << i + 1 << "\n";
                    break;
                }
            }
            --i;
        }
        if (found != 2)
            cout << "1\n";
    }
    return 0;
}

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

//----------------------------------- DEBUG -----------------------------------
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
// debug & operator << (debug & dd, P p) { dd << "(" << p.x << ", " << p.y << ")"; return dd; }

//----------------------------------- END DEBUG --------------------------------

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)

//----------------------------------- DEFINES ----------------------------------- 

#define sz(x) (int)(x).size()
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ins insert
#define nl '\n'

//----------------------------------- END DEFINES -------------------------------- 

//-------------------------- CUSTOM UNORDERED MAP HASH ---------------------------

struct custom_hash{
    static uint64_t splitmix64(uint64_t x){
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t a) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(a + FIXED_RANDOM);
    }
    template<class T> size_t operator()(T a) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        hash<T> x;
        return splitmix64(x(a) + FIXED_RANDOM);
    }
    template<class T, class H> size_t operator()(pair<T, H> a) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        hash<T> x;
        hash<H> y;
        return splitmix64(x(a.first) * 37 + y(a.second) + FIXED_RANDOM);
    }
};
template<class T, class H>using umap=unordered_map<T,H,custom_hash>;

//----------------------- CUSTOM UNORDERED MAP HASH END--------------------------

void run_cases() {
    int n;
    cin >> n;
    vector<int64_t> a(n);
    trav(u, a) cin >> u;

    if(n == 1) {
        cout << 0 << nl;
        return;
    }

    vector<int> bits(32, 0);
    for(auto u: a) {
        for(int64_t j=0;j<=31;j++) {
            if((u&(1LL << j)) != 0) {
                bits[j]++;
            }
        }
    }

    for(int i=31;i>=0;i--) {
        if(bits[i] >= 2) {
            cout << i + 1 << nl;
            return;
        }
    }
    cout << 1 << nl;
}   

int main() {
    ios_base::sync_with_stdio(0); cin.tie(nullptr);

    int tests = 1;
    cin >> tests;

    for(int test = 1;test <= tests;test++) {
        run_cases();
    }
}

Feel free to Share your approach, if you want to. (even if its same! ) . Suggestions are welcomed as always had been.