Count all ordered pairs with Bitwise And (&) equals to zero

Problem Statement-

You have been given an integer array A on size N . You must report the number of ordered pairs (i,j) such that A[i] & A[j] is zero .
Here ‘&’ denotes the BITWISE AND.
(i,j) and (j,i) are considered different.

**Input**
First line contains  **T** -Number of Test cases. First line of each test contains  **N** . Next line contains N integers - the i'th integer  **A[i]** .
**Output**
Output the number of such pairs for each test case.

**Constraints**  
**T ≤ 10**
**N ≤ 100000**
**A[i] ≤ 1000000**

example -
Input-
1
5
41 47 34 40 29
Output-
2

Link to the problem- https://www.hackerearth.com/challenges/competitive/think-a-thon/algorithm/special-pairs-7/

Looking for help @anon55659401 @ssjgz @vijju123 @l_returns

1 Like

It wants me to log in to view the problem, but it looks like the Think-A-Thon challenge is over.

Knee-jerk response: would treating the numbers as binary strings and adding them to a Trie be of use?

2 Likes

Yeah the challenge is very old, it’s long been since it was over(2015). I thought of a Trie solution and proceeded as follows-

  1. Converted each number to it’s Binary String and added it to a trie.
  2. Then for each number tried searching into the Trie, but I don’t know how to actually proceed with the search cause if some bit in the current number is 0 then it means both numbers having 0 as well as 1 bit corresponding to this bit can be a valid candidate to form pair with the current number. This in worst case has 2 possibilities for each bit, so, 2 ^ log2(K), K is the highest number.
    So, I don’t think I am getting anywhere with using a Trie, maybe I am applying Trie wrong altogether and there is some other way.
1 Like

@anon55659401 and @l_returns and @silver_surfer - was anyone able to come up with a clever, elegant solution to this?

I think I’ve got an exceedingly crap one that should (probably) be fast enough, though I haven’t tried to analyse it properly.

It’s based on

  • Writing each element of a as a 20-bit binary number
  • “Bucketing” each element of a into one of 2048 buckets based on the first half (i.e. first 10 bits) of its binary representation. Actually, we don’t bucket the whole of each element of a - we discard the first half/ 10-bits of its representation
  • Only comparing elements in buckets i and j such that i \mathbin{\&} j == 0 (surprisingly few such pairs)
  • Actually, we don’t fully compare elements - each bucket has, for each x = 0, … 2048, a lookup of how many elements of a in that bucket have element-of-a-with-first-10-bits-removed \mathbin{\&} x == 0.

Here’s the code, such as it is:

Ugly Solution
// Simon St James (ssjgz) - 2019-08-28
//
// Solution for "Special Pairs" - https://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/practice-problems/algorithm/special-pairs-7/
//
#define SUBMISSION
#define BRUTE_FORCE
#ifdef SUBMISSION
#undef BRUTE_FORCE
#define NDEBUG
#endif
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#include <cassert>

#include <sys/time.h> // TODO - this is only for random testcase generation.  Remove it when you don't need new random testcases!

using namespace std;

constexpr int maxAValue = 1'000'000;
constexpr int log2(int N, int exponent = 0, int powerOf2 = 1)
{
            return (powerOf2 >= N) ? exponent : log2(N, exponent + 1, powerOf2 * 2);
}
constexpr int maxNumBitsInA = log2(maxAValue);


template <typename T>
T read()
{
    T toRead;
    cin >> toRead;
    assert(cin);
    return toRead;
}

int64_t solveBruteForce(const vector<int>& a)
{
    int64_t result = 0;

    for (int i = 0; i < a.size(); i++)
    {
        for (int j = 0; j < a.size(); j++)
        {
            if ((a[i] & a[j]) == 0)
                result++;
        }
    }

    return result;
}

string asBinary(int64_t value)
{
    string asBinary;
    while (asBinary.size() < maxNumBitsInA)
    {
        asBinary.push_back(static_cast<char>('0' + (value & 1)));
        value >>= 1;
    }
    reverse(asBinary.begin(), asBinary.end());
    return asBinary;
};

int64_t solveOptimised(const vector<int>& a)
{
    assert(maxNumBitsInA % 2 == 0);
    const int halfBinaryNumBits = maxNumBitsInA / 2;
    const int halfBinaryMax = 1 << (halfBinaryNumBits + 1);
    struct Bucket
    {
        Bucket()
            : numSecondHalvesOfAThatGiveZeroWhenAndedWith(halfBinaryMax)
        {
        }
        vector<int> secondHalvesOfAInBucket;
        vector<int> numSecondHalvesOfAThatGiveZeroWhenAndedWith;
    };
    vector<Bucket> buckets(halfBinaryMax);

    // The "values" are between 0 and halfBinaryMax.
    vector<vector<int>> valuesThatGiveZeroWhenAndedWith(halfBinaryMax);

    for (int i = 0; i < halfBinaryMax; i++)
    {
        for (int j = 0; j < halfBinaryMax; j++)
        {
            if ((i & j) == 0)
            {
                valuesThatGiveZeroWhenAndedWith[i].push_back(j);
            }
        }

    }

    for (const auto aElement : a)
    {
        const int bucket = (aElement & (((static_cast<int64_t>(1) << (halfBinaryNumBits + 1)) - 1) << halfBinaryNumBits)) >> halfBinaryNumBits;
        const int secondHalfOfA = aElement & ((1 << (halfBinaryNumBits + 1)) - 1);
        assert(0 <= bucket && bucket < buckets.size());
        assert(0 <= secondHalfOfA && secondHalfOfA < halfBinaryMax);
        buckets[bucket].secondHalvesOfAInBucket.push_back(secondHalfOfA);
        for (const auto x : valuesThatGiveZeroWhenAndedWith[secondHalfOfA])
        {
            buckets[bucket].numSecondHalvesOfAThatGiveZeroWhenAndedWith[x]++;
        }
    }

    int64_t result = 0;
    for (int i = 0; i < buckets.size(); i++)
    {
        for (int j = 0; j < buckets.size(); j++)
        {
            if ((i & j) == 0)
            {
                // The first halves of any pair of elements of a from bucket[i] and bucket[j] will
                // "and" to 0 - what about the second halves?
                for (const auto secondHalfOfA : buckets[i].secondHalvesOfAInBucket)
                {
                    result += buckets[j].numSecondHalvesOfAThatGiveZeroWhenAndedWith[secondHalfOfA];
                }
            }
        }

    }

    return result;
}


int main(int argc, char* argv[])
{
    ios::sync_with_stdio(false);
    if (argc == 2 && string(argv[1]) == "--test")
    {
        struct timeval time;
        gettimeofday(&time,NULL);
        srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

        const int T = 10;
        cout << T << endl;
        for (int t = 0; t < T; t++)
        {
            const int N = 100'000;
            const int maxA = rand() % 1'000'000 + 1;
            cout << N << endl;
            for (int i = 0; i < N; i++)
            {
                cout << (rand() % maxA) << " ";
            }
            cout << endl;
        }
        return 0;
    }

    const int T = read<int>();

    for (int t = 0; t < T; t++)
    {
        const int N = read<int>();
        vector<int> a(N);
        for (auto& aElement : a)
        {
            aElement = read<int>();
        }

#ifdef BRUTE_FORCE
        const auto solutionBruteForce = solveBruteForce(a);
        cout << "solutionBruteForce: " << solutionBruteForce << endl;
        const auto solutionOptimised = solveOptimised(a);
        cout << "solutionOptimised: " << solutionOptimised << endl;

        assert(solutionOptimised == solutionBruteForce);
#else
        const auto solutionOptimised = solveOptimised(a);
        cout << solutionOptimised << endl;
#endif
    }

    assert(cin);
}

I’ll be very, very disappointed if this is the way that it is supposed to be solved.

3 Likes

I read somewhere that it is a SOS DP Problem.

1 Like

What’s “SOS”? :slight_smile: 20 characters blah-de-blah

2 Likes

Sum over Subset. Basically it’s a kind of DP + Bitmask. There is an awesome tutorial at Codeforces, Google it and the first link will be that.

1 Like

Did this solutions of yours get AC?

Dunno - don’t have a Hackerearth account :slight_smile:

1 Like

https://codeforces.com/blog/entry/20174
https://www.geeksforgeeks.org/number-ordered-pairs-ai-aj-0/
These links provide an elegant solution I think.

4 Likes

I was busy with life and still haven’t read the question :stuck_out_tongue:

2 Likes

The naive solution is to count all the pairs (i, j) such that A[i] & A[j] = 0 . But of course, it would time out given the constraints. A smarter way is to think in term of bits. The upper bound on the range of numbers is 10^{6}, so, 21 bits would suffice to store any integer in the range, the maximum number that you can represent using 21 bits is 11.....(repeated 21 times), i.e. 1048576, for representation purpose let’s call it MAX. So, we think of every number of the array represented in 21 bits, if some number requires less than 21 bit for representation, we pad rest of the bit after MSB with 0.
Now, for some A[i], A[i] & x = 0 will be satisfied by all those x, where-

  1. If some bit is set in A[i], then it must be unset in x, otherwise the bitwise & at this bit would be 1 and the overall result of A[i] & x would be non-zero.
  2. If some bit is unset in A[i] then this bit can be both set and unset in x.
    Now, if we flip all the 21 bits of A[i], i.e. turn zeros to one and vice versa, the above twi conditions get reversed, for representation purpose, let’s call ~A[i] as the bit-flipped version of A[i], then.-
  3. If some bit is set in ~A[i], then this bit can be both unset and set in x.
  4. If some bit is unset in ~A[i] then this bit must be unset in x.

If you have already worked with bitmasks a bit, then you can realise that we already getting somewhere, every number in the array satisfying the above two conditions can be called as a sub-mask of ~A[i]. But how do, we get ~A[i] from A[i]? It’s easy just XOR A[i] with 11.....(repeated 21 times) i.e. 1048576 or MAX as we denoted it above.

So, the entire task reduces to counting the sum frequency of sub-masks of ~A[i] for every A[i] in the array. And this is where SOS Dynamic Programming Comes into the picture. SOS DP let’s you compute the aggregation of some property over all subsets of a set, and since many sets can share the same subset, we can use DP. All we need is to smartly iterate over the subsets, so, we can form a recurrence relation.
See this tutorial on SOS DP for detail - https://codeforces.com/blog/entry/45223
Here is my accepted solution to the question - https://www.hackerearth.com/submission/35295515/

1 Like