# Find the bitwise AND of a subarray closest to given number

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

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.

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.

• Nice. This looks like the algorithm that is critically better that brute force with regard to the given bounds (and the missing time limit). – Apass.Jack Apr 16 at 12:04
• If the tables were initialised to zero, one could skip setting "wider entries" known to be sub-optimal (if f(36, 40) is too small, so will be f(32, 40), f(32, 48), f(32, 64), f(0, 64), f(0,128),…). Won't save more than half table setup effort.) – greybeard Apr 19 at 9:57

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.

• It looks like your algorithm runs in $O(n^2)$ in worst cases. Can you improve it to $O(n\log n)$ or even $O(n)$? Or can you explain your algorithm is not $O(n^2)$? I will upvote then. – Apass.Jack Apr 14 at 15:23
• (Bad case: alternating between two values greater than P.) – greybeard Apr 19 at 9:32