We have an array of N integers and Q queries. In each query, we are given an integer X. For each query, we have to output the number of unordered pairs in array that sum to X.

How can we efficiently answer these sort of queries?

Constraints:

1 <= N <= 2 * 10⁵

1 <= Q <= 2 * 10⁵

1 <= |a_i| <= 10¹⁸

1 <= X <= 10¹⁸

In problems involving bit masking, sometimes you might need to generate all submasks for a given mask.

Mask is nothing but a specific pattern of bits you use for some desired operation. For eg. to turn on 4th bit(0 based indexing) of a given number, you can use the mask 10000 (16 in decimal) and OR with the given number.

Submask of a given mask is nothing but a mask whose set bits are a subset of the given mask. For eg., 1010, 1000, 0010 are submasks of 1011, while 1100 is not a submask.

Now our problem is to generate all submasks for a given mask. We can solve this problem easily using recursion generating all submasks, but there’s a concise and elegant way of doing the same. We will discuss that here.

Consider the mask 10110 (22 in decimal). All the submasks of the given mask are 10110, 10100, 10010, 00110, 10000, 00100, 00010 and 00000.

We know that subtracting 1 from a given number unsets the rightmost set bit and sets all the unset bits after it.

For eg. 12 in binary is 1100, now when we subtract 1 from it, we get 11 (1011 in binary). Consider another example as 20 (10100). On subtracting 1, we get 19 (10011).

We can exploit this behavior to solve our problem of generating all submasks. If we subtract 1 from our mask and then AND with the original mask, we will end up with a submask with it’s rightmost set bit unset. Continuing our example of 10110 (22 in decimal), after subtracting 1, we will get 10101 and ANDing it with original mask 10110, we get 10100 which is one of the required submask. We keep on doing the same operation until we end up with 0.

If you didn’t understand, give it a dry run generating all 8 submasks and you will get it.

Here’s the simple code.

I learnt this simple yet surprising technique from a random leetcode article and felt worth sharing.

Hello

Can anyone please share resources regarding Fibonacci Bisection and some related problems and applications?