Find the bitwise AND of a subarray closest to given number

Question

It was a question I was asked in an online assessment for a company.

Please help me in this question-

Given an array, $A$ of size $N$ and an integer $P$ , find the subarray $B = A[i \dots j]$ such that $i \leq j$ and compute the bitwise value of subarray elements i.e say $K = B[i] \mathbin{\&}B [i+1] \mathbin{\&} \cdots \mathbin{\&}B[j]$.

Output the minimum value of $|K-P|$ among all values of $K$.

Size of array: $1 \leq A.\mathrm{size} \leq 100000$

$0\le A[i]\le 10^8$

I could only think of brute force.

Answer 1

Let f (i, j) = AND ($A_i, A_{i+1}, ..., A_{j-1})$ for $0 ≤ i < j ≤ n$. $f (i, j)$ has the property that whenever $i ≤ i' < j' ≤ j$, $f (i, j) ≤ f (i', j')$.

We also have $f (i, j)$ = AND($(f (i, k), f (k, j)$) for any $0 ≤ i < k < j ≤ n$.

Because of these properties, we get an algorithm slightly better than brute force as follows:

Keep track of the optimal solution so far, initialising with f (0, 1). For 0 ≤ i < n: If $a_i ≤ P$ then check if f (i, i+1) is a better solution. Otherwise, find the largest j such that f (i, j) ≥ P; it may be that j = n. Check if f (i, j) is a better solution. If j < n then check if f (i, j+1) < P is a better solution.

How to find the largest j in O (log n), making the total time O (n log n):

We start by building some tables, calculating all f (i, i+2) for even i, f (i, i+4) for i multiple of 4, f (i, i+8) for i multiple of 8. This is done in O (n) since there are about n values which can each be calculated with a single AND operation.

To find the largest j, we start with j = i+1, f (i, j) = a [i]. If j < n is odd then we can calculate f (i, j+1); if the result is ≥ P then we replace j with j+1, which makes j even. Then if j < n is an odd multiple of 2 we can calculate f (i, j+2); if the result is ≥ P then we replace j with j+1, which makes j a multiple of 4, and so on. This ends with j being a multiple of $2^k$ for some k. Now we try to increase j by $2^{k-1}$, $2^{k-2}$, ..., 4, 2, 1 if the increased j is ≤ n, and f (i, j) ≥ P. The total cost is O (log n) operations.

Answer 2

It is a nice question, because the problem is so useless that nobody has encountered it in practice, and it tests your ability to come up with algorithms on the spot.

You can use brute force with shortcuts. Let d = minimum of abs (P - K) found so far, then the AND of a subarray must be between max (P - d, 0) and P + d). To have a start value, find the single value k = A[i] closest to P, and the best solution so far is A [i:i].

The AND of a subarray only gets smaller if you add more array elements. So you do the brute force thing, starting with A[0:0], A[0:1], ... A [0..n-1], updating d if you have an improved value, and stopping when the AND is less than P-d. Let's say A[i:j-1] is > P-d but A[i:j] isn't, then you set i=j and decrease i as long as A[i+j] > d. You work out the details.

Note: This is obviously $O(n^2)$ but might be better. Hard to prove. And I suspect it is reasonably good for random data. It may not be an appropriate question for an online assessment, but better as an interview question where you can watch what the candidate does.