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**
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-
Converted each number to it’s Binary String and added it to a trie.
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.
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.
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-
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.
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.-
If some bit is set in ~A[i], then this bit can be both unset and set in x.
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 - SOS Dynamic Programming [Tutorial] - Codeforces
Here is my accepted solution to the question - https://www.hackerearth.com/submission/35295515/
20 characters blah-de-blah